typescript ThreeSum

时间:2022-09-28 东东么么哒人气:0

前言

本文执行环境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]]

加载全部内容