18、四数之和

鲁迅说过，人生的道路在于积累，而不是奇迹。每天进步一点点，相信自己，你

可以的。今天继续来刷《二哥的 LeetCode 刷题笔记》吧，冲鸭。

题意

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下

述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]（若两个四元组元

素一一对应，则认为两个四元组重复）：

1. $ 0 <= a, b, c, d < n $

2. a、b、c 和 d 互不相同

3. $ nums[a] + nums[b] + nums[c] + nums[d] == target $

你可以按 任意顺序 返回答案 。

难度

中等

示例

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

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

输入：nums = [2,2,2,2,2], target = 8

输出：[[2,2,2,2]]

分析 1

好家伙，解完两数之和来三数之和，解完三数之和来四数之和，是要我底掌握加法算啊（

这） 们彻底 掌 握 加 法 运算 啊 （ ?）

还记得三数之和的解法吗？我们先对数组进行排序，然后使用 for 循环确定其中一个数，

接着使用双指针法，找出剩下的两个数，使得三个数的和等于 target。

018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C-20240130073117.png

针对四数之和，我们可以采用同样的套路，先对数组进行排序，然后使用第一层 for 循环

确定其中一个数，再用第二层 for 循环确定第二个数，接着使用双指针法，找出剩下的两

个数，使得四个数的和等于 target。

来看题解：

class Solution {

public List<List<Integer>> fourSum(int[] nums, int target) {

// 先排序

Arrays.sort(nums);

List<List<Integer>> result = new ArrayList<>();

// 确定第一个数

for (int i = 0; i < nums.length - 3; i++) {

// 跳过重复的数字

if (i > 0 && nums[i] == nums[i - 1]) continue;

// 确定第二个数

for (int j = i + 1; j < nums.length - 2; j++) {

// 同样跳过重复的数字

if (j > i + 1 && nums[j] == nums[j - 1]) continue;

// 双指针找出剩下的两个数

int left = j + 1, right = nums.length - 1;

while (left < right) {

// 四数之和

int sum = nums[i] + nums[j] + nums[left] + nums[right];

 // 找到了

if (sum == target) {

// 添加到结果集中

result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

// 跳过重复的数字

while (left < right && nums[left] == nums[left + 1]) left++;

while (left < right && nums[right] == nums[right - 1]) right--;

left++;

right--;

} else if (sum < target) {

left++;// 和小于 target，左指针右移，变大点

} else {

right--;// 和大于 target，右指针左移，变小点

}

}

}

}

return result;

}

}

题解几乎和之前的三数之和一模一样，只是多了一层 for 循环，毕竟多了一个数，多了一

层循环也是应该的。

不过很遗憾，有一个测试用例没通过，四个 1000000000 相加会超过 int 类型的最大值

（大约是 21 亿），导致溢出。

018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C-20240130074553.png

也就是说，我们在计算 int 之和时，最好使用更大的类型，比如说 long 来容纳四数之和，

这样就不会溢出了。

class Solution {

public List<List<Integer>> fourSum(int[] nums, int target) {

// 先排序

Arrays.sort(nums);

List<List<Integer>> result = new ArrayList<>();

// 确定第一个数

for (int i = 0; i < nums.length - 3; i++) {

// 跳过重复的数字

if (i > 0 && nums[i] == nums[i - 1]) continue;

// 确定第二个数

for (int j = i + 1; j < nums.length - 2; j++) {

// 同样跳过重复的数字

if (j > i + 1 && nums[j] == nums[j - 1]) continue;

// 双指针找出剩下的两个数

int left = j + 1, right = nums.length - 1;

while (left < right) {

// 四数之和

long sum = (long)(nums[i]) + nums[j] + nums[left] + nums[right];

// 找到了

if (sum == target) {

// 添加到结果集中

result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

// 跳过重复的数字

while (left < right && nums[left] == nums[left + 1]) left++;

while (left < right && nums[right] == nums[right - 1]) right--;

left++;

right--;

} else if (sum < target) {

left++;// 和小于 target，左指针右移，变大点

} else {

right--;// 和大于 target，右指针左移，变小点

}

}

}

}

return result;

}

}

注意这行代码：long sum = (long)(nums[i]) + nums[j] + nums[left] + nums[right]; ，

首先 (long) nums[i] 将 nums[i] 转换为 long 型，接下来，由于加法是从左到右进行的，

所以当 nums[j] 加到 (long) nums[i] 上时，nums[j] 也会被提升为 long 型（这是因为在加

法中，两个操作数中有一个是 long 型时，另一个会自动提升为 long 型）。这个类型提升

和加法的顺序会继续应用于 nums[left] 和 nums[right]。因此，整个表达式的计算结果是

long 型，避免了溢出。

关于基本数据类型的强制类型转换和隐式类型转换，我在《二哥的 Java 进阶之路》上有

详细讲过，戳链接直达。

来看下题解效率，不是特别高：

018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C-20240130091725.png

分析 2

双指针本身已经是解决此类问题的最佳方案了，为什么效率还不够高呢？

主要在于我们没有对一些边界条件进行优化，比如说第一层 for 循环确定第一个数时：

• 假设 s = nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] ，如果 s > target，

由于数组是排过序的，意味着我们无法找到和为 target 的四个数了，可以直接跳出

了。

• 假设 s = nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] ，如果 s < target，

由于数组是排过序的，意味着第一个数太小了，我们直接进行下一轮循环即可。

同理，第二层 for 循环确定第二个数时：

• 假设 s = nums[i] + nums[j] + nums[j + 1] + nums[j + 2] ，如果 s > target，由于

数组是排过序的，意味着我们无法找到和为 target 的四个数了，可以直接跳出了。

• 假设 s = nums[i] + nums[j] + nums[n - 2] + nums[n - 1] ，如果 s < target，由于

数组是排过序的，意味着第二个数太小了，我们直接进行下一轮循环即可。

OK，我们来看下优化后的代码：

class Solution {

public List<List<Integer>> fourSum(int[] nums, int target) {

Arrays.sort(nums);

List<List<Integer>> result = new ArrayList<>();

int n = nums.length;

for (int i = 0; i < n - 3; i++) {

// 跳过重复元素

if (i > 0 && nums[i] == nums[i - 1]) continue;

// 提前结束循环的条件

if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)

break;

if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target)

continue;

for (int j = i + 1; j < n - 2; j++) {

// 跳过重复元素

if (j > i + 1 && nums[j] == nums[j - 1]) continue;

 // 同样的提前结束循环条件

if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)

break;

if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target)

continue;

int left = j + 1, right = n - 1;

while (left < right) {

long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

if (sum == target) {

result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

while (left < right && nums[left] == nums[left + 1]) left++;

while (left < right && nums[right] == nums[right - 1]) right--;

left++;

right--;

} else if (sum < target) {

left++;

} else {

right--;

}

}

}

}

return result;

}

}

效率提升了不少：

018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C-20240130094552.png

总结

这道题本身并没有什么亮点，仍然是双指针，只不过比三数之和多了一层 for 循环。

不过，边界条件的优化直接提升了一大截的效率，着实有点意外，按理说，算法题不应该

在这种细枝末节上大做文章，毕竟核心算法并没有什么改变。

本题涉及到的 Java 基础知识点比三数之和多了基本数据类型的类型转换，大家一定要注

意：

• 基本数据类型的强制类型转换和隐式类型转换

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