前言
本文执行环境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内容请搜索Devmax以前的文章或继续浏览下面的相关文章希望大家以后多多支持Devmax！