8804-两数之和

题目描述

给定一个整数数组 nums 和一个目标整数 target, 如果 nums 数组中存在两个元素的和等于 target 返回 true, 否则返回 false

分析

这个题目涉及到了加法，前面有提到过，ts 没有提供计算的能力，一般都是通过构造辅助元组的方式来进行计数，通过元组的长度来作为结果。

那么要实现加法，可以构造两个长度为 A,B 的元组，将元组组合起来，就是加法的结果。

// 创建长度为 A 的元组
type BuildArrs<
  A extends number,
  Arr extends any[] = [],
> = Arr['length'] extends A ? Arr : BuildArrs<A, [...Arr, 1]>;

// 加法就是将两个元组合并
type Sum<A extends number, B extends number> = [
  ...BuildArrs<A>,
  ...BuildArrs<B>,
]['length'];

这就构建了本题的基础，那么要判断是否存在两个数，和等于目标值，只需要遍历元组，在剩余元素中能够找到和当前元素和为目标值的元素，就为 true，否则就需要继续遍历下一个元素。

而判断剩余元素中，是否有和当前元素相加等于目标值，又需要遍历剩余元素，所以存在两次遍历，拆成两部分实现。

题解

// 创建长度为 A 的元组
type BuildArrs<
  A extends number,
  Arr extends any[] = [],
> = Arr['length'] extends A ? Arr : BuildArrs<A, [...Arr, 1]>;

// 加法就是将两个元组合并
type Sum<A extends number, B extends number> = [
  ...BuildArrs<A>,
  ...BuildArrs<B>,
]['length'];

// 判断 A 中是否存在一个元素，和 B 相加 = T
type Sums<A extends number[], B extends number, T extends number> = A extends [
  infer F extends number,
  ...infer R extends number[],
]
  ? Sum<F, B> extends T
    ? true
    : Sums<R, B, T>
  : false;

type TwoSum<T extends number[], U extends number> = T extends [
  infer F extends number,
  ...infer R extends number[],
]
  ? // 如果剩余元素中，存在一个元素和 F 相加 = U ，那么就返回true
    Sums<R, F, U> extends true
    ? true
    : // 否则递归剩余元素
      TwoSum<R, U>
  : false;

知识点

1. 元组辅助计数
2. 加法实现