018.四数之和
作者：沉默王二
发布时间：2024-01-30T09:55:54.968+0800
鲁迅说过，人生的道路在于积累，而不是奇迹。每天进步一点点，相信自己，你可以的。今天继续来刷《二哥的 LeetCode 刷题笔记》吧，冲鸭。
技术派阅读地址：https://paicoding.com/column/7/18
-
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
-
这道题可以说完全重写了，给出 1道大家完全都能掌握的题解（双指针）。
-
增加代码注释，这样大家更容易看懂并掌握题解；
-
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
-
增加手绘图，这样大家更容易理解解题思路；
-
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
-
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
-
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
-
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
鲁迅说过，人生的道路在于积累，而不是奇迹。每天进步一点点，相信自己，你可以的。今天继续来刷《二哥的 LeetCode 刷题笔记》吧，冲鸭。
题意
给你一个由 n 个整数组成的数组 nums ，和一个目标值target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
- 0<=a,b,c,d<n
- a、b、c 和 d 互不相同
- nums[a]+nums[b]+nums[c]+nums[d]==target
你可以按 任意顺序 返回答案 。
难度
中等
示例
输入：nums = [1,0,-1,0,-2,2], target = 0
输入：nums = [2,2,2,2,2], target = 8输出：[[2,2,2,2]]
分析 1
好家伙，解完**两数之和 来三数之和 ，解完三数之和 来四数之和 **，这是要我们彻底掌握加法运算啊（😂）
还记得三数之和的解法吗？我们先对数组进行排序，然后使用 for 循环确定其中一个数，接着使用双指针法，找出剩下的两个数，使得三个数的和等于 target。
针对四数之和，我们可以采用同样的套路，先对数组进行排序，然后使用第一层 for 循环确定其中一个数，再用第二层 for 循环确定第二个数，接着使用双指针法，找出剩下的两个数，使得四个数的和等于 target。
来看题解：
class Solution {
// 先排序 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 亿），导致溢出。
也就是说，我们在计算 int 之和时，最好使用更大的类型，比如说 long 来容纳四数之和，这样就不会溢出了。
class Solution {
// 先排序 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 进阶之路》上有详细讲过，**戳链接 **直达。
来看下题解效率，不是特别高：
分析 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 {
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; }}
效率提升了不少：
总结
这道题本身并没有什么亮点，仍然是双指针，只不过比**三数之和 **多了一层 for 循环。
不过，边界条件的优化直接提升了一大截的效率，着实有点意外，按理说，算法题不应该在这种细枝末节上大做文章，毕竟核心算法并没有什么改变。
本题涉及到的 Java 基础知识点比三数之和多了基本数据类型的类型转换，大家一定要注意：
力扣链接：https://leetcode.cn/problems/4sum/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
鲁迅说过，人生的道路在于积累，而不是奇迹。每天进步一点点，相信自己，你可以的。今天继续来刷《二哥的 LeetCode 刷题笔记》吧，冲鸭。
技术派阅读地址：https://paicoding.com/column/7/18
-
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
-
这道题可以说完全重写了，给出 1道大家完全都能掌握的题解（双指针）。
-
增加代码注释，这样大家更容易看懂并掌握题解；
-
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
-
增加手绘图，这样大家更容易理解解题思路；
-
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
-
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
-
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
-
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
鲁迅说过，人生的道路在于积累，而不是奇迹。每天进步一点点，相信自己，你可以的。今天继续来刷《二哥的 LeetCode 刷题笔记》吧，冲鸭。
题意
给你一个由 n 个整数组成的数组 nums ，和一个目标值target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
- 0<=a,b,c,d<n
- a、b、c 和 d 互不相同
- nums[a]+nums[b]+nums[c]+nums[d]==target
你可以按 任意顺序 返回答案 。
难度
中等
示例
输入：nums = [1,0,-1,0,-2,2], target = 0
输入：nums = [2,2,2,2,2], target = 8输出：[[2,2,2,2]]
分析 1
好家伙，解完**两数之和 来三数之和 ，解完三数之和 来四数之和 **，这是要我们彻底掌握加法运算啊（😂）
还记得三数之和的解法吗？我们先对数组进行排序，然后使用 for 循环确定其中一个数，接着使用双指针法，找出剩下的两个数，使得三个数的和等于 target。
针对四数之和，我们可以采用同样的套路，先对数组进行排序，然后使用第一层 for 循环确定其中一个数，再用第二层 for 循环确定第二个数，接着使用双指针法，找出剩下的两个数，使得四个数的和等于 target。
来看题解：
class Solution {
// 先排序 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 亿），导致溢出。
也就是说，我们在计算 int 之和时，最好使用更大的类型，比如说 long 来容纳四数之和，这样就不会溢出了。
class Solution {
// 先排序 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 进阶之路》上有详细讲过，**戳链接 **直达。
来看下题解效率，不是特别高：
分析 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 {
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; }}
效率提升了不少：
总结
这道题本身并没有什么亮点，仍然是双指针，只不过比**三数之和 **多了一层 for 循环。
不过，边界条件的优化直接提升了一大截的效率，着实有点意外，按理说，算法题不应该在这种细枝末节上大做文章，毕竟核心算法并没有什么改变。
本题涉及到的 Java 基础知识点比三数之和多了基本数据类型的类型转换，大家一定要注意：
力扣链接：https://leetcode.cn/problems/4sum/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
鲁迅说过，人生的道路在于积累，而不是奇迹。每天进步一点点，相信自己，你可以的。今天继续来刷《二哥的 LeetCode 刷题笔记》吧，冲鸭。
技术派阅读地址：https://paicoding.com/column/7/18
-
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
-
这道题可以说完全重写了，给出 1道大家完全都能掌握的题解（双指针）。
-
增加代码注释，这样大家更容易看懂并掌握题解；
-
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
-
增加手绘图，这样大家更容易理解解题思路；
-
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
-
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
-
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
-
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
鲁迅说过，人生的道路在于积累，而不是奇迹。每天进步一点点，相信自己，你可以的。今天继续来刷《二哥的 LeetCode 刷题笔记》吧，冲鸭。
题意
给你一个由 n 个整数组成的数组 nums ，和一个目标值target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
- 0<=a,b,c,d<n
- a、b、c 和 d 互不相同
- nums[a]+nums[b]+nums[c]+nums[d]==target
你可以按 任意顺序 返回答案 。
难度
中等
示例
输入：nums = [1,0,-1,0,-2,2], target = 0
输入：nums = [2,2,2,2,2], target = 8输出：[[2,2,2,2]]
分析 1
好家伙，解完**两数之和 来三数之和 ，解完三数之和 来四数之和 **，这是要我们彻底掌握加法运算啊（😂）
还记得三数之和的解法吗？我们先对数组进行排序，然后使用 for 循环确定其中一个数，接着使用双指针法，找出剩下的两个数，使得三个数的和等于 target。
针对四数之和，我们可以采用同样的套路，先对数组进行排序，然后使用第一层 for 循环确定其中一个数，再用第二层 for 循环确定第二个数，接着使用双指针法，找出剩下的两个数，使得四个数的和等于 target。
来看题解：
class Solution {
// 先排序 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 亿），导致溢出。
也就是说，我们在计算 int 之和时，最好使用更大的类型，比如说 long 来容纳四数之和，这样就不会溢出了。
class Solution {
// 先排序 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 进阶之路》上有详细讲过，**戳链接 **直达。
来看下题解效率，不是特别高：
分析 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 {
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; }}
效率提升了不少：
总结
这道题本身并没有什么亮点，仍然是双指针，只不过比**三数之和 **多了一层 for 循环。
不过，边界条件的优化直接提升了一大截的效率，着实有点意外，按理说，算法题不应该在这种细枝末节上大做文章，毕竟核心算法并没有什么改变。
本题涉及到的 Java 基础知识点比三数之和多了基本数据类型的类型转换，大家一定要注意：
力扣链接：https://leetcode.cn/problems/4sum/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412