使用typescript类型实现ThreeSum

目录

• 前言
• 思路整理
• 实现TwoSum
• 实现减法
• 元祖中是否包含差值
• 递归元组
• 测试
• 实现ThreeSum
• 实现排序
• 实现ThreeSum
• 测试

前言

本文执行环境typescript，版本4.7.4

不使用typescript的计算能力，通过类型来实现ThreeSum

思路整理

实现ThreeSum之前我们先降低下难度，实现TwoSum，因为TwoSum可以作为ThreeSum的基础泛型

TwoSum需要准备什么呢？

• 递归元组，模拟for循环
• 减法，递归过程中求出差值
• 对每一项差值判断是否存在

完成TwoSum后如何实现ThreeSum？

• 每一项和剩余元组走一遍 TwoSum泛型，筛选满足条件的
• 为了保证每一项能够走TwoSum泛型，对于元组大到小排序

实现TwoSum

实现减法

因为元组下标是递增有序数列，我们在每次递归的时候返回一个长度+1的新元组并获取长度，就可以对非负整数依次点名了

如求A - B，我们假设A - B永远是非负整数数，无限递归产生新元祖的过程中，排查掉A和B相等后，必定是先点名到B，然后点名到A，而B 到 A的递归次数就是差值，也就是求得的结果

实现这个差值的计算

• A作为被减数，R作为长度与减数相等的数组，Z则用于递归累增
• 当被减数R长度等于A的过程中，Z则是被减数和减数的差值

type GetLen<A extends number, R extends number[], Z extends number[] = []> =
  A extends R['length'] ? Z['length'] : GetLen<A, [...R, 0], [...Z, 0]>;

减法如下：

• 排除掉A和B相等的情况
• 前提条件：A大于或者等于B
• 用差值泛型求A 和 B的差

type Subtract<A extends number, B extends number, R extends number[] = []> =
  A extends B ? 0 :
  A extends R['length'] ? never :
  B extends R['length'] ? GetLen<A, R> :
  Subtract<A, B, [...R, 0]>;

元祖中是否包含差值

求出每一项的差值后，需要判断元组中是否存在，存在则满足 被减数和减数 都存在元祖，作为复合条件的一组返回

• 从元祖第一项开始递归至末尾，则返回false
• 若某一项的值满足寻找的值，返回ture，否则递归

type Includes<A extends number[], T extends number, L extends number[] = []> =
  A['length'] extends L['length'] ? false :
  A[L['length']] extends T ? true : Includes<A, T, [...L, 0]>;

递归元组

根据最开始的思路可以实现：

• 依次递归元祖
• 对每一项求差值
• 判断差值是否存在于数组中
• R是返回的结果，N是递归计数，Item是被减数，SubItem是减数

type TwoSum<
  T extends number,
  L extends number[],
  R extends number[][] = [],
  N extends number[] = [],
  Item extends number = L[N['length']],
  SubItem extends number = Subtract<T, Item>,
> = L['length'] extends N['length'] ?
  R : TwoSum<
    T,
    L,
    Includes<L, SubItem> extends true ? [
      ...R,
      [Item, SubItem]
    ] : R,
    [...N, 0]
  >;

type t1 = TwoSum<4, [1, 2, 3]>;
// [[1, 3], [2, 2], [3, 1]]

存在缺陷：

• 如果被减数和减数值相同，且只存在一个，那结果也是满足的。如：4 和 [1, 2, 3]，我们要的是 [1, 3]，需要排除掉 [2, 2]
• 递归到被减数和减数都会满足条件，会存在重复的两个结果。如：4 和 [1, 2, 3]，我们要的是 [1, 3]，需要排除掉 [3, 1]

出现这两个问题，是因为递归过的被减数仍然保留在元祖中，所以我们需要把递归过的被减数移除掉

优化一下：

• 每次递归后移除当前项

type GetNext<T extends number[]> = T extends [number, ...infer U] ? U : [];

type TwoSum<
  T extends number,
  L extends number[],
  R extends number[][] = [],
  Item extends number = L[0],
  SubItem extends number = Subtract<T, Item>,
  NextL extends number[] = GetNext<L>,
> = L['length'] extends 0 ?
  R : TwoSum<
    T,
    NextL,
    Includes<NextL, SubItem> extends true ? [
      ...R,
      [Item, SubItem]
    ] : R
  >;

测试

type t1 = TwoSum<7, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
// [[0, 7], [1, 6], [2, 5], [3, 4]]

type t2 = TwoSum<12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
// [[3, 9], [4, 8], [5, 7]]

type t3 = TwoSum<20, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
// []

type t4 = TwoSum<10, [0, 8, 2, 1, 4, 7, 6, 3, 4, 9]>;
// [[8, 2], [1, 9], [4, 6], [7, 3], [6, 4]]

实现ThreeSum

实现排序

之前已经实现typescript的快排，移步：用typescript类型来实现快排

为什么需要实现排序，因为上文中 TwoSum泛型的实现，需要满足

• 输入参数 - 被减数 = 减数。所以 输入参数 > 被减数 、 输入参数 > 减数
• 从头选取参数、被减数、减数

所以排序后可以直接使用TwoSum泛型

实现ThreeSum

• 递归元祖
• 依次选择 TwoSum的参数，剩余元组
• 剩余元组中挑选符合条件的被减数、减数并返回
• R为返回结果，NextL为剩余元组，NewList为合并TwoSum的结果

// 合并参数到TwoSum的结果，因为TwoSum返回的二元数组
type GetNewList<
  A extends number,
  T extends number[][],
  N extends number[] = [],
  R extends number[][] = []
> = T['length'] extends N['length'] ? R :
  GetNewList<A, T, [...N, 0], [...R, [A, ...T[N['length']]]]>;

type IsArray<T> = T extends number[] ? T : [];

type IsArray2<T> = T extends number[][] ? T : [];

type ThreeSumLoop<
  L extends number[],
  R extends number[][] = [],
  NextL extends number[] = GetNext<L>,
  NewList extends number[][] = IsArray2<TwoSum<L[0], NextL>>
> = L['length'] extends 0 | 1 ? R :
  ThreeSumLoop<NextL, NewList['length'] extends 0 ? R :
  IsArray2<[...R, ...GetNewList<L[0], NewList>]>>;

type ThreeSum<L extends number[]> = ThreeSumLoop<IsArray<QuickSort<L>>>;

测试

type l1 = ThreeSum<[1, 3, 2, 4]>;
// [[4, 3, 1], [3, 2, 1]]

type l2 = ThreeSum<[1, 6, 3, 7, 5, 4, 2]>;
// [[7, 6, 1], [7, 5, 2], [7, 4, 3], [6, 5, 1], [6, 4, 2], [5, 4, 1], [5, 3, 2], [4, 3, 1], [3, 2, 1]]

type l3 = ThreeSum<[0, 5, 15, 10, 5, 25, 20]>;
// [[25, 20, 5], [25, 15, 10], [20, 15, 5], [15, 10, 5], [10, 5, 5], [5, 5, 0]]

type l4 = ThreeSum<[1, 16, 3, 17, 5, 4, 21]>;
// [[21, 17, 4], [21, 16, 5], [17, 16, 1], [5, 4, 1], [4, 3, 1]]

到此这篇关于使用typescript类型实现ThreeSum的文章就介绍到这了,更多相关typescript ThreeSum内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！