15、三数之和

鲁迅说过，不经一番寒彻骨，怎得梅花扑鼻香。两数之和都搞定了，三数之和也

不在话下，今天就让我们继续来刷《二哥的 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]

输出：[[-1,-1,2],[-1,0,1]]

解释：

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 {

// 定义一个方法 twoSum，接收一个整数数组 nums 和一个目标值 target

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 {

public List<List<Integer>> threeSum(int[] nums) {

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);，就会出现这样的错误：

015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C-20240125121301.png

因为 [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% 的对手。

015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C-20240125143455.png

分析 2

我们再来看一下题目，题目要求我们找出所有和为 0 且不重复的三元组，那么我们可以先

将数组排序，然后固定一个数，再去找另外两个数。

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

在这种方法中，先用一个 for 循环遍历数组，对于每个数字，使用双指针在数组的剩余部

分查找和为 0 的另外两个元素。

class Solution {

// 定义 threeSum 方法找到所有不重复的三元组，它们的和为 0

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。

1. 固定一个数：让我们固定第一个数为 -4，即 nums[i] = -4。

2. 设置双指针：设置 left 指向 i + 1（即 -1），right 指向数组的最后一个元素（即

2）。

3. 开始寻找：

– 计算和：-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 相遇，结束这一轮查找。

4. 固定下一个数：固定下一个数（第二个 -1），重复上述过程。

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

nums[right]。

while (lo < hi && nums[lo] == nums[lo + 1]) lo++;

while (lo < hi && nums[hi] == nums[hi - 1]) hi--;

注意题解中的两个 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, -1, 2]。

2. 跳过重复的 **nums[lo]**：

– 当前 lo 指向第二个 -1，而 nums[lo + 1] 也是 -1。

– 我们继续移动 lo 指针，直到 nums[lo] 不再是 -1。

– 在这个例子中，所有的 -1 都被跳过了。

3. 跳过重复的 **nums[hi]**：

– 当前 hi 指向第一个 2，而 nums[hi - 1] 也是 2。

– 我们继续移动 hi 指针，直到 nums[hi] 不再是 2。

– 在这个例子中，所有的 2 都被跳过了。

通过这种方式，我们避免了例如 [-1, -1, 2]（使用了三个 -1 中的两个）和 [-1, 2, 2]（使用

了两个 2）这样重复的三元组出现在结果中。

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

015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C-20240125151609.png

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

手。

015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C-20240125151726.png

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

但 ArrayList 慢了 10%。

015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C-20240125152934.png

大家可以戳这里了解一下 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/