引言

大家好啊，我是前端拿破轮😁。

跟着卡哥学算法有一段时间了，通过代码随想录的学习，受益匪浅，首先向卡哥致敬🫡。

但是在学习过程中我也发现了一些问题，很多当时理解了并且AC的题目过一段时间就又忘记了，或者不能完美的写出来。根据费曼学习法，光有输入的知识掌握的是不够牢靠的，所以我决定按照代码随想录的顺序，输出自己的刷题总结和思考。同时，由于以前学习过程使用的是JavaScript,而在2025年的今天，TypeScript几乎成了必备项，所以本专题内容也将使用TypeScript，来巩固自己的TypeScript语言能力。

题目信息

三数之和

leetcode题目链接

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

题目分析

如何理解不能重复？

本题和两数之和一样，都是经典的面试题目，但是解法却不尽相同。关键就是本题要求的不能重复。这里的不能重复有几个层面的含义，都理解清楚才能帮助我们更准确地解题。

  1. 题目要求i!=j,i!=k,j!=k,这意味着在同一个三元组中，同一个元素只能使用一次。比如下面的例子
1
const arr = [1, -2, 3, 4];

这个数组中就没有符合题目要求的三元组。有同学可能会想我把1用两次，-2用一次，的到三元组[1, 1, -2]不就行了吗？然而实际上这是不符合要求的。因为这个意味着这个三元组是[nums[0], nums[0], nums[1]]。即i=j=0, k=1.这和题目要求的i!=j矛盾，所以不行。

但是这里要注意，题目要求的是在同一个三元组中，同一个元素只能使用一次。但是不同元素是可以多次使用的，哪怕他们的值一样。比如下面的例子:

1
const arr = [1, 1, -2, 3, 4];

这个例子比上面的例子多增加了一个1，就可以构建三元组[1, 1, -2]了。有同学可能要说，你这不对啊，你这1和1不是重复了吗。有这样困惑的同学，就是审题又错了。题目要求i!=j，没要求num[i]!=nums[j]啊。在本例中如果构建三元组 [1, 1, -2]，实际上就是[nums[0], nums[1], nums[2]],即i=0, j=1, k=2.很显然这是符合题目要求的。

这是第一个不能重复，就是在同一个三元组中，同一个元素只能使用一次

  1. 题目要求答案中不可以包含重复的三元组。就是字面意思，最后的结果数组中不能包含长得一样的数组*。比如下面的例子
1
const arr = [0, 0, 0, 0, 0]

这个数组中有5个0，但是最后符合条件的三元组个数并不是从中计算出的组合数$C_5^3 = 10$种，实际上只有1种，就是[0, 0, 0]，因为别的和它长得一样。

所以这是本题中不能重复的亮点核心理解。

双指针思路如何？

所以本题的解法是双指针。在写双指针之前一定要对数组进行排序。因为只有排序的数组，它的值才有一致的趋势，才能靠移动指针的方式来找到所有的组合。否则指针移动过程中所指的元素一会增大一会减小根本无法判断应该如何移动指针。

对数组进行排序后，先遍历三数之和中第一个数的位置。在遍历第一个数的位置的过程中也要进行剪枝和去重。

所谓剪枝，就是在确定后续循环肯定不会符合条件的情况下，提前跳出循环。比如我们对数组进行排序后，让元素呈现非递减顺序。然后从小到大遍历第一个元素的起始位置，如果当前元素已经大于0了，拿就可以直接结束循环了。因为后续的元素只会更大，三数之和肯定不会等于0.

所谓去重，就是最后的三元组中不能包含长得一样的数组，那么如果当前遍历的元素和前一个元素一样，则可以直接跳过本次循环。

在遍历第一个元素的循环内部，创建左右双指针。当前第一元素下标为i，则左指针为i + 1， 右指针始终从指向数组中最后一个元素的位置开始。

在左指针小于右指针的情况下，求出三数之和，并根据和的情况进行不同的判断。

如果和等于0，则将当前的三元组加入到结果数组中，并同时移动左右指针。因为当前和为0，如果只移动左指针，和一定大于0，只移动右指针，和一定小于0，只有同时移动左右指针才有可能让和等于0。同时对left和right进行去重。

如果和小于0，则移动左指针，反之，则移动右指针。

注意，只有在和等于0的情况下才需对左右指针进行去重，否则会遗漏某些值。比如下面的例子是一个排序过后的数组：

1
const arr = [-3, -1, -1, 0, 0, 1, 2, 3];

如果此时i=1,left=2，right=7,即i指向-1，left指向-1，right指向3.如果此时由于nums[left]和nums[left-1]的值相等就移动left进行去重，那么就会漏掉后续的[-1, -1, 2]这个组合。那为什么sum等于0的情况下进行去重就不会漏掉呢？因为这种情况下已经把当前的三元组加入了结果数组，所以不会漏掉。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
function threeSum(nums: number[]): number[][] {
    // 排序
    nums.sort((a, b) => a - b);

    // 结果数组
    const result = [];

    // 遍历起始位置
    for (let i = 0; i < nums.length; i++) {
        // 剪枝
        if (nums[i] > 0) break;
        
        // 去重
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        // 左右指针
        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            // 计算三数之和
            const sum = nums[i] + nums[left] + nums[right];

            // 根据sum的大小进行不同操作
            if (sum === 0) {
                // 将结果加入数组
                result.push([nums[i], nums[left], nums[right]]);

                // 移动指针
                left++;
                right--;

                // 注意，只有在sum===0时再进行左右指针的去重，否则可能导致遗漏解
                while (left < right && nums[left] === nums[left - 1]) left++;
                while (left < right && nums[right] === nums[right + 1]) right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
};

时间复杂度：$O(n^2)$, 排序为$O(nlogn)$,遍历第一个元素内部再嵌套双指针为$O(n^2)$.总的复杂度是$O(n^2)$

空间复杂度：$O(1)$,只用两个指针，常数级别的空间复杂度。

总结

为什么不用哈希表？

有同学可能会想，既然本题和两数之和类似，为什么不用map哈希表呢？

主要就是因为题目中的不能重复，所以如果使用哈希表还需要对哈希表中的结果进行去重，导致时间复杂度升高。此外，哈希表会占用额外的空间，空间复杂度也弱于双指针。

下面提供哈希表版题解，大家可以自行研究。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b); // 排序是去重前提
    const res: number[][] = [];
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) break; // 剪枝：首数大于0则无解
        if (i > 0 && nums[i] === nums[i - 1]) continue; // 去重：a 的重复值跳过[3,5](@ref)
        
        const seen = new Set<number>(); // 存储可能的 c 值
        for (let j = i + 1; j < nums.length; j++) {
            // 去重：跳过连续重复的 b（允许相邻重复一次）
            if (j > i + 2 && nums[j] === nums[j - 1] && nums[j - 1] === nums[j - 2]) {
                continue;
            }
            
            const complement = -nums[i] - nums[j]; // c = -a - b
            if (seen.has(complement)) {
                res.push([nums[i], nums[j], complement]);
                // 去重：c 使用后立即移除，避免重复组合[2,3](@ref)
                seen.delete(complement); 
            } else {
                seen.add(nums[j]); // 未匹配时记录当前 b 值
            }
        }
    }
    return res;
}

为什么两数之和不能用双指针？

到这里可能有的同学又有疑惑，既然双指针这么好，为什么两数之和不用双指针呢？主要是因为两数之和要求返回的是有效的下标。而使用双指针法必须排序。一旦排序，下标信息就会丢失，无法返回。如果两数之和要求返回的是两数本身的话，也可以使用双指针。此外对于两数之和来说，使用哈希表可以实现O(n)的时间复杂度，而如果使用双指针，光排序就要O(nlogn)，也不是很划算。

好了，这篇文章就到这里啦，如果对您有所帮助，欢迎点赞,收藏,分享👍👍👍。您的认可是我更新的最大动力。由于笔者水平有限，难免有疏漏不足之处，欢迎各位大佬评论区指正。

往期推荐✨✨✨

我是前端拿破轮，关注我，一起学习前端知识，我们下期见！