当前位置：首页 > TypeScript > TypeScript 类型体操：利用编译期类型实现 ThreeSum 算法

TypeScript 类型体操：利用编译期类型实现 ThreeSum 算法

作者：小括号时间：2026-10-25 18:24:46浏览：184

本文基于 TypeScript 4.7.4 版本，展示如何在编译期利用类型系统实现 ThreeSum 算法。通过构建 TwoSum 泛型作为基础，利用元组递归模拟循环、计算差值并判断元素存在性，最终结合排序逻辑完成三元组查找。文章详细解析了类型递归、元组操作及去重优化的具体实现细节。

前言

本文基于 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。
  • 若某一项的值满足寻找的目标值，返回 true，否则继续递归。
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内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！

作者最新文章

JS语法错误会阻止加载吗？区分SyntaxError与资源加载失败

2026-11-05 16:08:46

JavaScript常见SyntaxError语法错误排查与修复方法

2026-11-05 13:58:44

JS中slice、substring和substr截取字符串的区别

2026-11-05 13:43:47

JS 转 TS 手动迁移最佳实践：从配置 tsconfig 到消除 any 类型

2026-11-05 11:53:32

为什么JS数组push后得到的是数字而不是数组？

2026-11-05 09:59:18

相关文章
更多