TS 类型体操实现 TwoSum

题目

1. 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

2. 示例

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

3. 示例

输入：nums = [3,2,4], target = 6
输出：[1,2]

4. 示例

输入：nums = [3,3], target = 6
输出：[0,1]

原题解法

function twoSum(nums, target) {
    if(nums.length === 0) return false
    let temp = [];
    for(let i=0;i<nums.length;i++){
        // 计算期望值
        let dif = target - nums[i];
        if(temp[dif]){
            return [temp[dif],i];
        }
        temp[nums[i]] = i;
    }
    return false
}

typescript 类型体操版

为了简化思路,这里只需要返回 true 或者 false 即可

改为 Function 类型解法

function twoSumFunctional(nums, target, set = []) {
  if (nums.length === 0) return false
  const dif = target - nums[0]
  return set.includes(dif) || twoSumFunctional(nums.slice(1), target, [...set, nums[0]])
}

由 Function 类型解法改为类型体操版本

// 实现减法
type ToTuple<L extends number, T extends any[] = []> = T['length'] extends L
  ? T
  : ToTuple<L, [...T, any]>
type to = ToTuple<3> // [any,any,any]

type Sub<A extends number, B extends number> = ToTuple<A> extends [...ToTuple<B>, ...(infer Rest)]
  ? Rest['length']
  : -1
type sub = Sub<5, 2> // 3

// 实现slice
type Tail<T> = T extends [any, ...(infer Tail)] ? Tail : []
type tail = Tail<[1, 2, 3, 4]> // [2,3,4]

// 利用 '1' extends '1' | '2' 为true 实现includes , 利用 | 收集 dif
type TwoSum<N extends number[], T extends number, Set = never> = N['length'] extends 0
  ? false
  : Sub<T, N[0]> extends Set
  ? true
  : TwoSum<Tail<N>, T, Set | N[0]>
type sum = TwoSum<[1, 2, 3], 4> // true

::: primary Typescript 类型体操训练 type-challenges :::