用typescript类型实现ThreeSum

本文作者： 东东么么哒

写在前面 本文执行环境typescript，版本4.7.4

---

简介

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

ThreeSum： 枚举一个数组中 a + b = c 的三元组数量，每个三元组都不重复

思路整理

实现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则是被减数和减数的差值

减法如下：

• 排除掉A和B相等的情况

• 前提条件：A大于或者等于B

• 用差值泛型求A 和 B的差

元组中是否包含差值

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

• 从元祖第一项开始递归至末尾，则返回false

• 若某一项的值满足寻找的值，返回ture，否则递归

递归元组

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

• 依次递归元祖

• 对每一项求差值

• 判断差值是否存在于数组中

• R是返回的结果，N是递归计数，Item是被减数，SubItem是减数

存在缺陷：

1. 如果被减数和减数值相同，且只存在一个，那结果也是满足的。如：4 和 [1, 2, 3]，我们要的是 [1, 3]，需要排除掉 [2, 2]

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

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

优化一下：

• 每次递归后移除当前项

测试

实现ThreeSum

排序

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

1. 输入参数 - 被减数 = 减数。所以 输入参数 > 被减数 、 输入参数 > 减数

1. 从头选取参数、被减数、减数

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

ThreeSum

• 递归元祖

• 依次选择 TwoSum的参数，剩余元组

• 剩余元组中挑选符合条件的被减数、减数并返回

• R为返回结果，NextL为剩余元组，NewList为合并TwoSum的结果

测试