015.三数之和

作者：沉默王二 发布时间：2024-01-25T16:03:14.478+0800

---

技术派阅读地址：https://paicoding.com/column/7/15

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出2道大家完全都能掌握的题解（哈希和双指针）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

鲁迅说过，不经一番寒彻骨，怎得梅花扑鼻香。两数之和都搞定了，三数之和也不在话下，今天就让我们继续来刷《二哥的 LeetCode 刷题笔记》。

题意

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

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

难度

中等

示例

输入：nums = [-1,0,1,2,-1,-4]

解释：nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意，输出的顺序和三元组的顺序并不重要。 输入：nums = [0,1,1]输出：[]解释：唯一可能的三元组和不为 0 。 输入：nums = [0,0,0]输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。

分析 1

三数之和，很容易就让我们想到**两数之和 **，都是在数组中找出满足某种条件的元素。但是这道题比两数之和要复杂一些，增加了一个数嘛。

如果想套用两数之和的思路，我们可以先固定一个数，然后再去找另外两个数，这样就可以转换为两数之和的问题了。

下面是两数之和的题解：

class Solution {

public int[] twoSum(int[] nums, int target) {        // 创建一个哈希表来存储数组元素和它们的索引        Map<Integer, Integer> map = new HashMap<>();        // 遍历数组中的每个元素        for(int i = 0; i < nums.length; i++){            // 计算与当前元素相配对的另一个元素的值            int complement = target - nums[i];            // 检查哈希表中是否已存在这个配对元素            if(map.containsKey(complement))                // 如果存在，返回当前元素的索引和配对元素的索引                return new int[]{i, map.get(complement)};            // 将当前元素及其索引添加到哈希表中            map.put(nums[i], i);        }        // 如果遍历完数组都没有找到符合条件的两个数，则抛出异常        throw new IllegalArgumentException("没找到");    }}

我们借助这个题解，来完成三数之和的题解：

class Solution {

    Set<List<Integer>> res = new HashSet<>();        // 遍历数组中的每个元素        for (int i = 0; i < nums.length - 1; i++) {            // 创建一个集合存储已经遍历过的数字，避免重复使用            Map<Integer, Integer> map = new HashMap<>();            for (int j = i + 1; j < nums.length; j++) {                int complement = -nums[i] - nums[j];                // 如果 complement 在集合中，说明找到了一组解                if (map.containsKey(complement)) {                    // 将结果添加到集合中，这里使用数组并排序是为了避免重复                    Integer[] temp = new Integer[]{nums[i], nums[j], complement};                    Arrays.sort(temp);                    res.add(Arrays.asList(temp));                }                // 将当前数字添加到集合中                map.put(nums[j], j);            }        }        return new ArrayList<>(res);    }}

思路如下：

①、第一层 for 循环，将 nums[i] 作为第一个数，然后再去找另外两个数。

②、第二层 for 循环，将 nums[j] 作为第二个数，然后再去找第三个数 int complement = -nums[i] - nums[j]。因为 nums[i] + nums[j] + nums[k] == 0，所以 nums[k] == -nums[i] - nums[j]。

③、如果 complement 在 Map 中，说明找到了一组解，将结果添加到 HashSet 中，这里使用数组并排序是为了避免重复。

假如我们把排序去掉 Arrays.sort (temp);，就会出现这样的错误：

因为 [0,-1,1],[-1,1,0] 本来算是一种结果 [-1,0,1]，不排序的话，就算是两种结果，都会放入 HashSet。

之所以用 HashSet，就是因为 HashSet 会自动去重，第二次 add [-1,0,1] 回覆盖第一次 add。这个我在《二哥的 Java 进阶之路 》里有详细讲过。

好，当输入是 [-1,0,1,2,-1,-4] 时，我们来模拟一下整个题解过程。

①、第一层 for 循环，将 nums[i] 作为第一个数，此时 nums[i] = -1，然后再去找另外两个数。

②、第二层 for 循环，将 nums[j] 作为第二个数，此时 nums[j] = 0，然后再去找第三个数 int complement = -nums[i] - nums[j] = 1。

把 nums[j] = 0 put 到 Map 中，此时 Map 的键中有 [0]。

继续内层循环，此时 nums[j] = 1，complement = -nums[i] - nums[j] = 0，发现 Map 中有 0，说明找到了一组解。把排序后的 [-1,0,1] 添加到 Set 中。把 nums[j] = 1 put 到 Map 中，此时 Map 的键中有 [0, 1]。

继续内层循环，此时 nums[j] = 2，complement = -nums[i] - nums[j] = -1，发现 Map 中没有 -1，把 nums[j] = 2 put 到 Map 中，此时 Map 的键中有 [0, 1, 2]。

继续内层循环，此时 nums[j] = -1，complement = -nums[i] - nums[j] = 2，发现 Map 中有 2，说明找到了一组解。把排序后的 [-1,-1,2] 添加到 Set 中。把 nums[j] = -1 put 到 Map 中，此时 Map 的键中有 [0, 1, 2, -1]。

继续内层循环，此时 nums[j] = -4，complement = -nums[i] - nums[j] = 3，发现 Map 中没有 3，把 nums[j] = -4 put 到 Map 中，此时 Map 的键中有 [0, 1, 2, -1, -4]。

③、内存循环结束，第一层循环继续，此时 nums[i] = 0，然后再去找另外两个数。

后续我就不再模拟了，大家可以推演一下。

整体上非常好理解，在两数之和上稍微多了一些处理，比如说用 Arrays.sort 排序数组，用 Set 去重，用 Map 存储已经遍历过的数字是之前两数之和就有的。

两层循环，外加排序、哈希表和 Set 去重，题解的效率不高，只能打败 5% 的对手。

分析 2

我们再来看一下题目，题目要求我们找出所有和为 0 且不重复的三元组，那么我们可以先将数组排序，然后固定一个数，再去找另外两个数。

双指针来解决三数之和是一个效率较高的选择。

在这种方法中，先用一个 for 循环遍历数组，对于每个数字，使用双指针在数组的剩余部分查找和为 0 的另外两个元素。

class Solution {

public List<List<Integer>> threeSum(int[] nums) {        // 先对数组进行排序        Arrays.sort(nums);        // 创建一个列表来保存结果        List<List<Integer>> res = new LinkedList<>();        // 遍历数组，注意我们要停在倒数第三个数，因为我们至少需要三个数        for (int i = 0; i < nums.length - 2; i++) {            // 如果当前数字大于0，则后面不可能有三个数加和等于0，直接返回结果            if (nums[i] > 0) break;            // 跳过数组中重复的元素            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {                int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];                // 开始两数之和的双指针搜索                while (lo < hi) {                    if (nums[lo] + nums[hi] == sum) {                        // 找到一组解                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));                        // 跳过重复值                        while (lo < hi && nums[lo] == nums[lo + 1]) lo++;                        while (lo < hi && nums[hi] == nums[hi - 1]) hi--;                        lo++; hi--;                    } else if (nums[lo] + nums[hi] < sum) {                        // 如果和小于 sum，移动左指针                        lo++;                    } else {                        // 如果和大于 sum，移动右指针                        hi--;                    }                }            }        }        // 返回结果        return res;    }}

①、排序数组：首先对数组进行排序。排序是使用双指针法的前提，它让我们能够应用双指针技术来避免不必要的重复检查，并且帮助我们更快地缩小搜索范围。

②、遍历数组：使用一个循环遍历数组，固定一个元素 nums[i] 作为三元组的第一个元素。

③、跳过重复元素：如果当前元素与前一个元素相同，则跳过，避免重复解。这样做的原因是：

• 当 nums[i] == nums[i - 1] 时，意味着我们之前已经考虑过以 nums[i - 1] 作为三元组第一个元素的所有可能组合。因此，以 nums[i] 作为第一个元素的所有组合也会与之前的组合重复。
• 为了避免这种重复，我们只在 nums[i] 与 nums[i - 1] 不同时，才考虑以 nums[i] 作为三元组的第一个元素。

假设有一个排序后的数组 [-1, -1, 0, 1, 1]：当 i = 1 时，nums[i] 和 nums[i - 1] 都是 -1。由于我们已经考虑了以第一个 -1 为第一个元素的所有三元组，所以我们跳过第二个 -1。

④、设置双指针：在 nums[i] 之后的数组中设置两个指针，一个指向开始位置 left = i + 1，另一个指向数组末尾 right = nums.length - 1。

⑤、查找和为目标值的元素：在循环中移动 left 和 right，如果 nums[i] + nums[left] + nums[right] 的和小于零，移动 left 指针；如果和大于零，移动 right 指针；如果和等于零，找到了有效的三元组，将其添加到结果中。

• 如果 a + b + c < 0，即和小于零，意味着我们需要一个更大的数来增加总和。由于数组已经排序，我们可以通过将 left 向右移动来增加 b 的值。
• 如果 a + b + c > 0，即和大于零，意味着我们需要一个更小的数来减少总和。同样，由于数组是排序的，我们可以通过将 right 向左移动来减少 c 的值。
• 如果 a + b + c = 0，我们找到了一个有效的三元组。

假设我们有一个排序后的数组 [-4, -1, -1, 0, 1, 2]，我们要找三个数的和为 0。

• 固定一个数：让我们固定第一个数为 -4，即 nums[i] = -4。
• 设置双指针：设置 left 指向 i + 1（即 -1），right 指向数组的最后一个元素（即 2）。
• 开始寻找：
• 计算和：-4 + (-1) + 2 = -3。和小于零，所以我们需要增加和。
• 将 left 向右移动到下一个 -1。
• 再次计算和：-4 + (-1) + 2 = -3。仍然小于零，继续移动 left。
• left 移动到 0，计算和：-4 + 0 + 2 = -2。仍然小于零，再次移动 left。
• left 移动到 1，计算和：-4 + 1 + 2 = -1。仍然小于零，继续移动 left。
• left 和 right 相遇，结束这一轮查找。
• 固定下一个数：固定下一个数（第二个 -1），重复上述过程。

⑤、跳过重复元素：在找到一个有效的三元组后，跳过重复的 nums[left] 和 nums[right]。

while (lo 

注意题解中的两个 while 循环，是用于跳过重复的元素，以防止在结果列表中出现重复的三元组。

- 对于 nums[lo]，如果下一个元素 nums[lo + 1] 与它相同，我们就继续将 lo 指针向右移动，直到 nums[lo] 不再与 nums[lo + 1] 相同。
- 对于 nums[hi]，如果前一个元素 nums[hi - 1] 与它相同，我们就继续将 hi 指针向左移动，直到 nums[hi] 不再与 nums[hi - 1] 相同。

假设有一个排序后的数组 [-1, -1, -1, 2, 2]，我们要找出所有和为 0 的三元组。

- **找到一个三元组**：假设我们固定第一个 -1，并且找到了一个三元组 [-1, -1, 2]。
- 跳过重复的 nums[lo]：
- 当前 lo 指向第二个 -1，而 nums[lo + 1] 也是 -1。
- 我们继续移动 lo 指针，直到 nums[lo] 不再是 -1。
- 在这个例子中，所有的 -1 都被跳过了。
- 跳过重复的 nums[hi]：
- 当前 hi 指向第一个 2，而 nums[hi - 1] 也是 2。
- 我们继续移动 hi 指针，直到 nums[hi] 不再是 2。
- 在这个例子中，所有的 2 都被跳过了。

通过这种方式，我们避免了例如 [-1, -1, 2]（使用了三个 -1 中的两个）和 [-1, 2, 2]（使用了两个 2）这样重复的三元组出现在结果中。

当我们把这两个 while 循环删除的话，来看一下结果，就一目了然了。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_15.png)

OK，到此为止，我们已经完成了三数之和的题解，题解的效率非常高，打败了 90% 的对手。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_16.png)

注意题解中我用了 LinkedList 而不是 ArrayList，按理说两个在时间效率上是差不多的，但 ArrayList 慢了 10%。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_17.png)

大家可以戳**[这里](https://javabetter.cn/collection/list-war-2.html)**了解一下 LinkedList 和 ArrayList 的区别。

注意题目的条件：3 <= [nums.length](http://nums.length) <= 3000，当数组的长度没有触发 ArrayList 的动态扩容时，效率应该是差不多的；但如果数组的长度很长很长，结果集非常非常多，触发了 ArrayList 的动态扩容，插入的效率就会低一些。

当然了，题解的效率也可能是 LeetCode 的计算结果有偏差。

### **总结**

对于题解 1 来说，很好掌握，因为有两数之和的基础，但效率不高。

对于题解 2 来说，边界条件有点多，比如说第一层 for 循环要以 [nums.length](http://nums.length) - 2 结束，因为三个数为一组嘛。

再比如说，for 循环中要跳过重复元素，所以要判断 i == 0 || (i > 0 && nums[i] != nums[i - 1])。

再再比如说，while 双指针中要移动左指针还是右指针，需要通过 nums[lo] + nums[hi] 和 sum 的大小关系来判断。

再再再比如说，while 双指针中要跳过重复元素，所以要判断 nums[lo] == nums[lo + 1] 和 nums[hi] == nums[hi - 1]。

但整体用到的 Java 基础知识其实不多，比如说：

- **[数组的排序和数组转 List](https://javabetter.cn/common-tool/arrays.html)**
- **[ArrayList 和 LinkedList](https://javabetter.cn/collection/list-war-2.html)**
- **[Set 和 Map](https://javabetter.cn/collection/gailan.html)**
- **[for 循环、while 循环、if 语句](https://javabetter.cn/basic-grammar/flow-control.html)**

力扣链接：**[https://leetcode.cn/problems/3sum/](https://leetcode.cn/problems/3sum/)**

### **一步一个脚印**

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**[二哥编程星球](https://javabetter.cn/zhishixingqiu/)**的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_18.png)

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

        
        

技术派阅读地址：[https://paicoding.com/column/7/15](https://paicoding.com/column/7/15)

- 语雀专栏地址+密码可通过星球置顶帖查看：[https://t.zsxq.com/15rEo9Pdu](https://t.zsxq.com/15rEo9Pdu)
- 这道题可以说完全重写了，给出2道大家完全都能掌握的题解（哈希和双指针）。

- 增加代码注释，这样大家更容易看懂并掌握题解；
- 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
- 增加手绘图，这样大家更容易理解解题思路；
- 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
- 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
- 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
- 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

鲁迅说过，不经一番寒彻骨，怎得梅花扑鼻香。两数之和都搞定了，三数之和也不在话下，今天就让我们继续来刷《二哥的 LeetCode 刷题笔记》。

### **题意**

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

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

### **难度**

中等

### **示例**

输入：nums = [-1,0,1,2,-1,-4]

解释：nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意，输出的顺序和三元组的顺序并不重要。
输入：nums = [0,1,1]输出：[]解释：唯一可能的三元组和不为 0 。
输入：nums = [0,0,0]输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

### **分析 1**

三数之和，很容易就让我们想到**[两数之和](https://paicoding.com/column/7/1)**，都是在数组中找出满足某种条件的元素。但是这道题比两数之和要复杂一些，增加了一个数嘛。

如果想套用两数之和的思路，我们可以先固定一个数，然后再去找另外两个数，这样就可以转换为两数之和的问题了。

下面是两数之和的题解：

class Solution {

    public int[] twoSum(int[] nums, int target) {        // 创建一个哈希表来存储数组元素和它们的索引        Map<Integer, Integer> map = new HashMap<>();        // 遍历数组中的每个元素        for(int i = 0; i < nums.length; i++){            // 计算与当前元素相配对的另一个元素的值            int complement = target - nums[i];            // 检查哈希表中是否已存在这个配对元素            if(map.containsKey(complement))                // 如果存在，返回当前元素的索引和配对元素的索引                return new int[]{i, map.get(complement)};            // 将当前元素及其索引添加到哈希表中            map.put(nums[i], i);        }        // 如果遍历完数组都没有找到符合条件的两个数，则抛出异常        throw new IllegalArgumentException("没找到");    }}

我们借助这个题解，来完成三数之和的题解：

class Solution {

        Set<List<Integer>> res = new HashSet<>();        // 遍历数组中的每个元素        for (int i = 0; i < nums.length - 1; i++) {            // 创建一个集合存储已经遍历过的数字，避免重复使用            Map<Integer, Integer> map = new HashMap<>();            for (int j = i + 1; j < nums.length; j++) {                int complement = -nums[i] - nums[j];                // 如果 complement 在集合中，说明找到了一组解                if (map.containsKey(complement)) {                    // 将结果添加到集合中，这里使用数组并排序是为了避免重复                    Integer[] temp = new Integer[]{nums[i], nums[j], complement};                    Arrays.sort(temp);                    res.add(Arrays.asList(temp));                }                // 将当前数字添加到集合中                map.put(nums[j], j);            }        }        return new ArrayList<>(res);    }}

思路如下：

①、第一层 for 循环，将 nums[i] 作为第一个数，然后再去找另外两个数。

②、第二层 for 循环，将 nums[j] 作为第二个数，然后再去找第三个数 int complement = -nums[i] - nums[j]。因为 nums[i] + nums[j] + nums[k] == 0，所以 nums[k] == -nums[i] - nums[j]。

③、如果 complement 在 Map 中，说明找到了一组解，将结果添加到 HashSet 中，这里使用数组并排序是为了避免重复。

假如我们把排序去掉 [Arrays.sort](http://Arrays.sort)(temp);，就会出现这样的错误：

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_13.png)

因为 [0,-1,1],[-1,1,0] 本来算是一种结果 [-1,0,1]，不排序的话，就算是两种结果，都会放入 HashSet。

之所以用 HashSet，就是因为 HashSet 会自动去重，第二次 add [-1,0,1] 回覆盖第一次 add。这个我在《**[二哥的 Java 进阶之路](https://javabetter.cn/collection/gailan.html)**》里有详细讲过。

好，当输入是 [-1,0,1,2,-1,-4] 时，我们来模拟一下整个题解过程。

①、第一层 for 循环，将 nums[i] 作为第一个数，此时 nums[i] = -1，然后再去找另外两个数。

②、第二层 for 循环，将 nums[j] 作为第二个数，此时 nums[j] = 0，然后再去找第三个数 int complement = -nums[i] - nums[j] = 1。

把 nums[j] = 0 put 到 Map 中，此时 Map 的键中有 [0]。

继续内层循环，此时 nums[j] = 1，complement = -nums[i] - nums[j] = 0，发现 Map 中有 0，说明找到了一组解。把排序后的 [-1,0,1] 添加到 Set 中。把 nums[j] = 1 put 到 Map 中，此时 Map 的键中有 [0, 1]。

继续内层循环，此时 nums[j] = 2，complement = -nums[i] - nums[j] = -1，发现 Map 中没有 -1，把 nums[j] = 2 put 到 Map 中，此时 Map 的键中有 [0, 1, 2]。

继续内层循环，此时 nums[j] = -1，complement = -nums[i] - nums[j] = 2，发现 Map 中有 2，说明找到了一组解。把排序后的 [-1,-1,2] 添加到 Set 中。把 nums[j] = -1 put 到 Map 中，此时 Map 的键中有 [0, 1, 2, -1]。

继续内层循环，此时 nums[j] = -4，complement = -nums[i] - nums[j] = 3，发现 Map 中没有 3，把 nums[j] = -4 put 到 Map 中，此时 Map 的键中有 [0, 1, 2, -1, -4]。

③、内存循环结束，第一层循环继续，此时 nums[i] = 0，然后再去找另外两个数。

后续我就不再模拟了，大家可以推演一下。

整体上非常好理解，在两数之和上稍微多了一些处理，比如说用 [Arrays.sort](http://Arrays.sort) 排序数组，用 Set 去重，用 Map 存储已经遍历过的数字是之前两数之和就有的。

两层循环，外加排序、哈希表和 Set 去重，题解的效率不高，只能打败 5% 的对手。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_14.png)

### **分析 2**

我们再来看一下题目，题目要求我们找出所有和为 0 且不重复的三元组，那么我们可以先将数组排序，然后固定一个数，再去找另外两个数。

双指针来解决三数之和是一个效率较高的选择。

在这种方法中，先用一个 for 循环遍历数组，对于每个数字，使用双指针在数组的剩余部分查找和为 0 的另外两个元素。

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {        // 先对数组进行排序        Arrays.sort(nums);        // 创建一个列表来保存结果        List<List<Integer>> res = new LinkedList<>();        // 遍历数组，注意我们要停在倒数第三个数，因为我们至少需要三个数        for (int i = 0; i < nums.length - 2; i++) {            // 如果当前数字大于0，则后面不可能有三个数加和等于0，直接返回结果            if (nums[i] > 0) break;            // 跳过数组中重复的元素            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {                int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];                // 开始两数之和的双指针搜索                while (lo < hi) {                    if (nums[lo] + nums[hi] == sum) {                        // 找到一组解                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));                        // 跳过重复值                        while (lo < hi && nums[lo] == nums[lo + 1]) lo++;                        while (lo < hi && nums[hi] == nums[hi - 1]) hi--;                        lo++; hi--;                    } else if (nums[lo] + nums[hi] < sum) {                        // 如果和小于 sum，移动左指针                        lo++;                    } else {                        // 如果和大于 sum，移动右指针                        hi--;                    }                }            }        }        // 返回结果        return res;    }}

①、**排序数组**：首先对数组进行排序。排序是使用双指针法的前提，它让我们能够应用双指针技术来避免不必要的重复检查，并且帮助我们更快地缩小搜索范围。

②、**遍历数组**：使用一个循环遍历数组，固定一个元素 nums[i] 作为三元组的第一个元素。

③、**跳过重复元素**：如果当前元素与前一个元素相同，则跳过，避免重复解。这样做的原因是：

- 当 nums[i] == nums[i - 1] 时，意味着我们之前已经考虑过以 nums[i - 1] 作为三元组第一个元素的所有可能组合。因此，以 nums[i] 作为第一个元素的所有组合也会与之前的组合重复。
- 为了避免这种重复，我们只在 nums[i] 与 nums[i - 1] 不同时，才考虑以 nums[i] 作为三元组的第一个元素。

假设有一个排序后的数组 [-1, -1, 0, 1, 1]：当 i = 1 时，nums[i] 和 nums[i - 1] 都是 -1。由于我们已经考虑了以第一个 -1 为第一个元素的所有三元组，所以我们跳过第二个 -1。

④、**设置双指针**：在 nums[i] 之后的数组中设置两个指针，一个指向开始位置 left = i + 1，另一个指向数组末尾 right = [nums.length](http://nums.length) - 1。

⑤、**查找和为目标值的元素**：在循环中移动 left 和 right，如果 nums[i] + nums[left] + nums[right] 的和小于零，移动 left 指针；如果和大于零，移动 right 指针；如果和等于零，找到了有效的三元组，将其添加到结果中。

- 如果 a + b + c < 0，即和小于零，意味着我们需要一个更大的数来增加总和。由于数组已经排序，我们可以通过将 left 向右移动来增加 b 的值。
- 如果 a + b + c > 0，即和大于零，意味着我们需要一个更小的数来减少总和。同样，由于数组是排序的，我们可以通过将 right 向左移动来减少 c 的值。
- 如果 a + b + c = 0，我们找到了一个有效的三元组。

假设我们有一个排序后的数组 [-4, -1, -1, 0, 1, 2]，我们要找三个数的和为 0。

- **固定一个数**：让我们固定第一个数为 -4，即 nums[i] = -4。
- **设置双指针**：设置 left 指向 i + 1（即 -1），right 指向数组的最后一个元素（即 2）。
- **开始寻找**：
- 计算和：-4 + (-1) + 2 = -3。和小于零，所以我们需要增加和。
- 将 left 向右移动到下一个 -1。
- 再次计算和：-4 + (-1) + 2 = -3。仍然小于零，继续移动 left。
- left 移动到 0，计算和：-4 + 0 + 2 = -2。仍然小于零，再次移动 left。
- left 移动到 1，计算和：-4 + 1 + 2 = -1。仍然小于零，继续移动 left。
- left 和 right 相遇，结束这一轮查找。
- **固定下一个数**：固定下一个数（第二个 -1），重复上述过程。

⑤、**跳过重复元素**：在找到一个有效的三元组后，跳过重复的 nums[left] 和 nums[right]。

while (lo

注意题解中的两个 while 循环，是用于跳过重复的元素，以防止在结果列表中出现重复的三元组。

• 对于 nums[lo]，如果下一个元素 nums[lo + 1] 与它相同，我们就继续将 lo 指针向右移动，直到 nums[lo] 不再与 nums[lo + 1] 相同。
• 对于 nums[hi]，如果前一个元素 nums[hi - 1] 与它相同，我们就继续将 hi 指针向左移动，直到 nums[hi] 不再与 nums[hi - 1] 相同。

假设有一个排序后的数组 [-1, -1, -1, 2, 2]，我们要找出所有和为 0 的三元组。

• 找到一个三元组：假设我们固定第一个 -1，并且找到了一个三元组 [-1, -1, 2]。
• 跳过重复的 nums[lo]：
• 当前 lo 指向第二个 -1，而 nums[lo + 1] 也是 -1。
• 我们继续移动 lo 指针，直到 nums[lo] 不再是 -1。
• 在这个例子中，所有的 -1 都被跳过了。
• 跳过重复的 nums[hi]：
• 当前 hi 指向第一个 2，而 nums[hi - 1] 也是 2。
• 我们继续移动 hi 指针，直到 nums[hi] 不再是 2。
• 在这个例子中，所有的 2 都被跳过了。

通过这种方式，我们避免了例如 [-1, -1, 2]（使用了三个 -1 中的两个）和 [-1, 2, 2]（使用了两个 2）这样重复的三元组出现在结果中。

当我们把这两个 while 循环删除的话，来看一下结果，就一目了然了。

OK，到此为止，我们已经完成了三数之和的题解，题解的效率非常高，打败了 90% 的对手。

注意题解中我用了 LinkedList 而不是 ArrayList，按理说两个在时间效率上是差不多的，但 ArrayList 慢了 10%。

大家可以戳**这里 **了解一下 LinkedList 和 ArrayList 的区别。

注意题目的条件：3 <= nums.length <= 3000，当数组的长度没有触发 ArrayList 的动态扩容时，效率应该是差不多的；但如果数组的长度很长很长，结果集非常非常多，触发了 ArrayList 的动态扩容，插入的效率就会低一些。

当然了，题解的效率也可能是 LeetCode 的计算结果有偏差。

总结

对于题解 1 来说，很好掌握，因为有两数之和的基础，但效率不高。

对于题解 2 来说，边界条件有点多，比如说第一层 for 循环要以 nums.length - 2 结束，因为三个数为一组嘛。

再比如说，for 循环中要跳过重复元素，所以要判断 i == 0 || (i > 0 && nums[i] != nums[i - 1])。

再再比如说，while 双指针中要移动左指针还是右指针，需要通过 nums[lo] + nums[hi] 和 sum 的大小关系来判断。

再再再比如说，while 双指针中要跳过重复元素，所以要判断 nums[lo] == nums[lo + 1] 和 nums[hi] == nums[hi - 1]。

但整体用到的 Java 基础知识其实不多，比如说：

• 数组的排序和数组转 List
• ArrayList 和 LinkedList
• Set 和 Map
• for 循环、while 循环、if 语句

力扣链接：https://leetcode.cn/problems/3sum/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

技术派阅读地址：https://paicoding.com/column/7/15

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出2道大家完全都能掌握的题解（哈希和双指针）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

鲁迅说过，不经一番寒彻骨，怎得梅花扑鼻香。两数之和都搞定了，三数之和也不在话下，今天就让我们继续来刷《二哥的 LeetCode 刷题笔记》。

题意

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

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

难度

中等

示例

输入：nums = [-1,0,1,2,-1,-4]

解释：nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意，输出的顺序和三元组的顺序并不重要。 输入：nums = [0,1,1]输出：[]解释：唯一可能的三元组和不为 0 。 输入：nums = [0,0,0]输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。

分析 1

三数之和，很容易就让我们想到**两数之和 **，都是在数组中找出满足某种条件的元素。但是这道题比两数之和要复杂一些，增加了一个数嘛。

如果想套用两数之和的思路，我们可以先固定一个数，然后再去找另外两个数，这样就可以转换为两数之和的问题了。

下面是两数之和的题解：

class Solution {

public int[] twoSum(int[] nums, int target) {        // 创建一个哈希表来存储数组元素和它们的索引        Map<Integer, Integer> map = new HashMap<>();        // 遍历数组中的每个元素        for(int i = 0; i < nums.length; i++){            // 计算与当前元素相配对的另一个元素的值            int complement = target - nums[i];            // 检查哈希表中是否已存在这个配对元素            if(map.containsKey(complement))                // 如果存在，返回当前元素的索引和配对元素的索引                return new int[]{i, map.get(complement)};            // 将当前元素及其索引添加到哈希表中            map.put(nums[i], i);        }        // 如果遍历完数组都没有找到符合条件的两个数，则抛出异常        throw new IllegalArgumentException("没找到");    }}

我们借助这个题解，来完成三数之和的题解：

class Solution {

    Set<List<Integer>> res = new HashSet<>();        // 遍历数组中的每个元素        for (int i = 0; i < nums.length - 1; i++) {            // 创建一个集合存储已经遍历过的数字，避免重复使用            Map<Integer, Integer> map = new HashMap<>();            for (int j = i + 1; j < nums.length; j++) {                int complement = -nums[i] - nums[j];                // 如果 complement 在集合中，说明找到了一组解                if (map.containsKey(complement)) {                    // 将结果添加到集合中，这里使用数组并排序是为了避免重复                    Integer[] temp = new Integer[]{nums[i], nums[j], complement};                    Arrays.sort(temp);                    res.add(Arrays.asList(temp));                }                // 将当前数字添加到集合中                map.put(nums[j], j);            }        }        return new ArrayList<>(res);    }}

思路如下：

①、第一层 for 循环，将 nums[i] 作为第一个数，然后再去找另外两个数。

②、第二层 for 循环，将 nums[j] 作为第二个数，然后再去找第三个数 int complement = -nums[i] - nums[j]。因为 nums[i] + nums[j] + nums[k] == 0，所以 nums[k] == -nums[i] - nums[j]。

③、如果 complement 在 Map 中，说明找到了一组解，将结果添加到 HashSet 中，这里使用数组并排序是为了避免重复。

假如我们把排序去掉 Arrays.sort (temp);，就会出现这样的错误：

因为 [0,-1,1],[-1,1,0] 本来算是一种结果 [-1,0,1]，不排序的话，就算是两种结果，都会放入 HashSet。

之所以用 HashSet，就是因为 HashSet 会自动去重，第二次 add [-1,0,1] 回覆盖第一次 add。这个我在《二哥的 Java 进阶之路 》里有详细讲过。

好，当输入是 [-1,0,1,2,-1,-4] 时，我们来模拟一下整个题解过程。

①、第一层 for 循环，将 nums[i] 作为第一个数，此时 nums[i] = -1，然后再去找另外两个数。

②、第二层 for 循环，将 nums[j] 作为第二个数，此时 nums[j] = 0，然后再去找第三个数 int complement = -nums[i] - nums[j] = 1。

把 nums[j] = 0 put 到 Map 中，此时 Map 的键中有 [0]。

继续内层循环，此时 nums[j] = 1，complement = -nums[i] - nums[j] = 0，发现 Map 中有 0，说明找到了一组解。把排序后的 [-1,0,1] 添加到 Set 中。把 nums[j] = 1 put 到 Map 中，此时 Map 的键中有 [0, 1]。

继续内层循环，此时 nums[j] = 2，complement = -nums[i] - nums[j] = -1，发现 Map 中没有 -1，把 nums[j] = 2 put 到 Map 中，此时 Map 的键中有 [0, 1, 2]。

继续内层循环，此时 nums[j] = -1，complement = -nums[i] - nums[j] = 2，发现 Map 中有 2，说明找到了一组解。把排序后的 [-1,-1,2] 添加到 Set 中。把 nums[j] = -1 put 到 Map 中，此时 Map 的键中有 [0, 1, 2, -1]。

继续内层循环，此时 nums[j] = -4，complement = -nums[i] - nums[j] = 3，发现 Map 中没有 3，把 nums[j] = -4 put 到 Map 中，此时 Map 的键中有 [0, 1, 2, -1, -4]。

③、内存循环结束，第一层循环继续，此时 nums[i] = 0，然后再去找另外两个数。

后续我就不再模拟了，大家可以推演一下。

整体上非常好理解，在两数之和上稍微多了一些处理，比如说用 Arrays.sort 排序数组，用 Set 去重，用 Map 存储已经遍历过的数字是之前两数之和就有的。

两层循环，外加排序、哈希表和 Set 去重，题解的效率不高，只能打败 5% 的对手。

分析 2

我们再来看一下题目，题目要求我们找出所有和为 0 且不重复的三元组，那么我们可以先将数组排序，然后固定一个数，再去找另外两个数。

双指针来解决三数之和是一个效率较高的选择。

在这种方法中，先用一个 for 循环遍历数组，对于每个数字，使用双指针在数组的剩余部分查找和为 0 的另外两个元素。

class Solution {

public List<List<Integer>> threeSum(int[] nums) {        // 先对数组进行排序        Arrays.sort(nums);        // 创建一个列表来保存结果        List<List<Integer>> res = new LinkedList<>();        // 遍历数组，注意我们要停在倒数第三个数，因为我们至少需要三个数        for (int i = 0; i < nums.length - 2; i++) {            // 如果当前数字大于0，则后面不可能有三个数加和等于0，直接返回结果            if (nums[i] > 0) break;            // 跳过数组中重复的元素            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {                int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];                // 开始两数之和的双指针搜索                while (lo < hi) {                    if (nums[lo] + nums[hi] == sum) {                        // 找到一组解                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));                        // 跳过重复值                        while (lo < hi && nums[lo] == nums[lo + 1]) lo++;                        while (lo < hi && nums[hi] == nums[hi - 1]) hi--;                        lo++; hi--;                    } else if (nums[lo] + nums[hi] < sum) {                        // 如果和小于 sum，移动左指针                        lo++;                    } else {                        // 如果和大于 sum，移动右指针                        hi--;                    }                }            }        }        // 返回结果        return res;    }}

①、排序数组：首先对数组进行排序。排序是使用双指针法的前提，它让我们能够应用双指针技术来避免不必要的重复检查，并且帮助我们更快地缩小搜索范围。

②、遍历数组：使用一个循环遍历数组，固定一个元素 nums[i] 作为三元组的第一个元素。

③、跳过重复元素：如果当前元素与前一个元素相同，则跳过，避免重复解。这样做的原因是：

• 当 nums[i] == nums[i - 1] 时，意味着我们之前已经考虑过以 nums[i - 1] 作为三元组第一个元素的所有可能组合。因此，以 nums[i] 作为第一个元素的所有组合也会与之前的组合重复。
• 为了避免这种重复，我们只在 nums[i] 与 nums[i - 1] 不同时，才考虑以 nums[i] 作为三元组的第一个元素。

假设有一个排序后的数组 [-1, -1, 0, 1, 1]：当 i = 1 时，nums[i] 和 nums[i - 1] 都是 -1。由于我们已经考虑了以第一个 -1 为第一个元素的所有三元组，所以我们跳过第二个 -1。

④、设置双指针：在 nums[i] 之后的数组中设置两个指针，一个指向开始位置 left = i + 1，另一个指向数组末尾 right = nums.length - 1。

⑤、查找和为目标值的元素：在循环中移动 left 和 right，如果 nums[i] + nums[left] + nums[right] 的和小于零，移动 left 指针；如果和大于零，移动 right 指针；如果和等于零，找到了有效的三元组，将其添加到结果中。

• 如果 a + b + c < 0，即和小于零，意味着我们需要一个更大的数来增加总和。由于数组已经排序，我们可以通过将 left 向右移动来增加 b 的值。
• 如果 a + b + c > 0，即和大于零，意味着我们需要一个更小的数来减少总和。同样，由于数组是排序的，我们可以通过将 right 向左移动来减少 c 的值。
• 如果 a + b + c = 0，我们找到了一个有效的三元组。

假设我们有一个排序后的数组 [-4, -1, -1, 0, 1, 2]，我们要找三个数的和为 0。

• 固定一个数：让我们固定第一个数为 -4，即 nums[i] = -4。
• 设置双指针：设置 left 指向 i + 1（即 -1），right 指向数组的最后一个元素（即 2）。
• 开始寻找：
• 计算和：-4 + (-1) + 2 = -3。和小于零，所以我们需要增加和。
• 将 left 向右移动到下一个 -1。
• 再次计算和：-4 + (-1) + 2 = -3。仍然小于零，继续移动 left。
• left 移动到 0，计算和：-4 + 0 + 2 = -2。仍然小于零，再次移动 left。
• left 移动到 1，计算和：-4 + 1 + 2 = -1。仍然小于零，继续移动 left。
• left 和 right 相遇，结束这一轮查找。
• 固定下一个数：固定下一个数（第二个 -1），重复上述过程。

⑤、跳过重复元素：在找到一个有效的三元组后，跳过重复的 nums[left] 和 nums[right]。

while (lo 

注意题解中的两个 while 循环，是用于跳过重复的元素，以防止在结果列表中出现重复的三元组。

- 对于 nums[lo]，如果下一个元素 nums[lo + 1] 与它相同，我们就继续将 lo 指针向右移动，直到 nums[lo] 不再与 nums[lo + 1] 相同。
- 对于 nums[hi]，如果前一个元素 nums[hi - 1] 与它相同，我们就继续将 hi 指针向左移动，直到 nums[hi] 不再与 nums[hi - 1] 相同。

假设有一个排序后的数组 [-1, -1, -1, 2, 2]，我们要找出所有和为 0 的三元组。

- **找到一个三元组**：假设我们固定第一个 -1，并且找到了一个三元组 [-1, -1, 2]。
- 跳过重复的 nums[lo]：
- 当前 lo 指向第二个 -1，而 nums[lo + 1] 也是 -1。
- 我们继续移动 lo 指针，直到 nums[lo] 不再是 -1。
- 在这个例子中，所有的 -1 都被跳过了。
- 跳过重复的 nums[hi]：
- 当前 hi 指向第一个 2，而 nums[hi - 1] 也是 2。
- 我们继续移动 hi 指针，直到 nums[hi] 不再是 2。
- 在这个例子中，所有的 2 都被跳过了。

通过这种方式，我们避免了例如 [-1, -1, 2]（使用了三个 -1 中的两个）和 [-1, 2, 2]（使用了两个 2）这样重复的三元组出现在结果中。

当我们把这两个 while 循环删除的话，来看一下结果，就一目了然了。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_15.png)

OK，到此为止，我们已经完成了三数之和的题解，题解的效率非常高，打败了 90% 的对手。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_16.png)

注意题解中我用了 LinkedList 而不是 ArrayList，按理说两个在时间效率上是差不多的，但 ArrayList 慢了 10%。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_17.png)

大家可以戳**[这里](https://javabetter.cn/collection/list-war-2.html)**了解一下 LinkedList 和 ArrayList 的区别。

注意题目的条件：3 <= [nums.length](http://nums.length) <= 3000，当数组的长度没有触发 ArrayList 的动态扩容时，效率应该是差不多的；但如果数组的长度很长很长，结果集非常非常多，触发了 ArrayList 的动态扩容，插入的效率就会低一些。

当然了，题解的效率也可能是 LeetCode 的计算结果有偏差。

### **总结**

对于题解 1 来说，很好掌握，因为有两数之和的基础，但效率不高。

对于题解 2 来说，边界条件有点多，比如说第一层 for 循环要以 [nums.length](http://nums.length) - 2 结束，因为三个数为一组嘛。

再比如说，for 循环中要跳过重复元素，所以要判断 i == 0 || (i > 0 && nums[i] != nums[i - 1])。

再再比如说，while 双指针中要移动左指针还是右指针，需要通过 nums[lo] + nums[hi] 和 sum 的大小关系来判断。

再再再比如说，while 双指针中要跳过重复元素，所以要判断 nums[lo] == nums[lo + 1] 和 nums[hi] == nums[hi - 1]。

但整体用到的 Java 基础知识其实不多，比如说：

- **[数组的排序和数组转 List](https://javabetter.cn/common-tool/arrays.html)**
- **[ArrayList 和 LinkedList](https://javabetter.cn/collection/list-war-2.html)**
- **[Set 和 Map](https://javabetter.cn/collection/gailan.html)**
- **[for 循环、while 循环、if 语句](https://javabetter.cn/basic-grammar/flow-control.html)**

力扣链接：**[https://leetcode.cn/problems/3sum/](https://leetcode.cn/problems/3sum/)**

### **一步一个脚印**

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**[二哥编程星球](https://javabetter.cn/zhishixingqiu/)**的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

![图片](https://clxhuhhr.top/uploads/weblog/erge/erge_lc_image_18.png)

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

        
                
                
                知识星球
                
        
        
            
            扫码加入星球
            查看更多优质内容
        
        https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412