【LeetCode刷题日记】18.四数之和

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言前面我们刚刷完了三数之和这里我们继续学习四数之和看着是比三数之和更难一点但其实代码逻辑都是一样的让我们看看吧。摘要本文介绍了LeetCode 18题quot;四数之和quot;的解题思路与Java实现。该题要求在给定数组中找到所有不重复的四元组使其和等于目标值。解题采用双指针法在排序后的数组基础上通过两层循环固定前两个数再用双指针寻找后两个数同时进行剪枝优化和去重处理。时间复杂度为O(n³)与三数之和类似但多一层循环。文章详细解析了代码逻辑包括排序、双重循环、双指针移动、剪枝条件和去重操作并指出其可扩展性五数、六数之和等。最后提供了完整的Java代码示例和测试用例。题目背景LeetCode18给你一个由n个整数组成的数组nums和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]若两个四元组元素一一对应则认为两个四元组重复0 a, b, c, d na、b、c和d互不相同nums[a] nums[b] nums[c] nums[d] target你可以按任意顺序返回答案 。示例 1输入nums [1,0,-1,0,-2,2], target 0输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2输入nums [2,2,2,2,2], target 8输出[[2,2,2,2]]提示1 nums.length 200-109 nums[i] 109-109 target 109题目答案import java.util.*; public class Solution { public ListListInteger fourSum(int[] nums, int target) { Arrays.sort(nums); // 排序数组 ListListInteger result new ArrayList(); // 结果集 for (int k 0; k nums.length; k) { // 剪枝处理 if (nums[k] target nums[k] 0) { break; // 此处的break可以等价于return result; } // 对nums[k]去重 if (k 0 nums[k] nums[k - 1]) { continue; } for (int i k 1; i nums.length; i) { // 第二级剪枝 if (nums[k] nums[i] target nums[k] nums[i] 0) { break; // 注意是break到上一级for循环如果直接return result;会有遗漏 } // 对nums[i]去重 if (i k 1 nums[i] nums[i - 1]) { continue; } int left i 1; int right nums.length - 1; while (right left) { long sum (long) nums[k] nums[i] nums[left] nums[right]; if (sum target) { right--; } else if (sum target) { left; } else { result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right])); // 对nums[left]和nums[right]去重 while (right left nums[right] nums[right - 1]) right--; while (right left nums[left] nums[left 1]) left; right--; left; } } } } return result; } public static void main(String[] args) { Solution solution new Solution(); int[] nums {1, 0, -1, 0, -2, 2}; int target 0; ListListInteger results solution.fourSum(nums, target); for (ListInteger result : results) { System.out.println(result); } } }题目解析四数之和和15.三数之和是一个思路都是使用双指针法, 基本解法就是在15.三数之和 的基础上再套一层for循环。但是有一些细节需要注意例如不要判断nums[k] target就返回了三数之和 可以通过nums[i] 0就返回了因为 0 已经是确定的数了四数之和这道题目 target是任意值。比如数组是[-4, -3, -2, -1]target是-10不能因为-4 -10而跳过。但是我们依旧可以去做剪枝逻辑变成if (nums[i] 0 nums[i] target)break;就可以了。15.三数之和 的双指针解法是一层for循环num[i]为确定值然后循环内有left和right下标作为双指针找到nums[i] nums[left] nums[right] 0。四数之和的双指针解法是两层for循环nums[k] nums[i]为确定值依然是循环内有left和right下标作为双指针找出nums[k] nums[i] nums[left] nums[right] target的情况三数之和的时间复杂度是O(n^2)四数之和的时间复杂度是O(n^3) 。那么一样的道理五数之和、六数之和等等都采用这种解法。代码逻辑首先我们先排序数组然后创建一个结果集合用来存储结果。然后我们最外层的循环来遍历第一个元素负责选出四个数中的第一个关于第一层去重if (nums[k] target nums[k] 0) { break; // 此处的break可以等价于return result; }第一层的去重是为了提前结束相当于三数之和的第一个条件如果大于零直接返回。在这里我们的条件是要求nums[k]target,并且nums[k]0因为数组是按顺序排的然后呢这个nums[k]还是四个数中的第一个所以后面的三个数一定大于nums[k],况且nums[k]已经大于target了所以再寻找后面的三个元素已经是多余的了完全不存在的结果所以直接break。然后接下来就是// 对nums[k]去重 if (k 0 nums[k] nums[k - 1]) { continue;这个跟三数之和的去重逻辑一模一样如果当前第一个数 上一个第一个数直接跳过直接continue跳过不会重复生成答案 ✅然后就是第二级枝剪for (int i k 1; i nums.length; i) { // 第二级剪枝 if (nums[k] nums[i] target nums[k] nums[i] 0) { break; // 注意是break到上一级for循环如果直接return result;会有遗漏 }这个目的是为了寻找第二个元素固定前两个数之后发现这俩加起来已经太大了后面就不用找了直接跳出这层循环。一步步拆开讲k第一个数i第二个数这时候前两个数已经定下来了后面还有两个数left、right而且数组是排好序的。所以后面的数只会 ≥ 当前的数只会越来越大。然后就是对第二个元素进行去重// 对nums[i]去重 if (i k 1 nums[i] nums[i - 1]) { continue; }跟三数之和去重第二个元素一样再者之后我们去找第三个和第四个数int left i 1; int right nums.length - 1;找到这四个数字我们计算总和sum之后进行比较while (right left) { long sum (long) nums[k] nums[i] nums[left] nums[right]; if (sum target) { right--; } else if (sum target) { left; } else { result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right])); // 对nums[left]和nums[right]去重 while (right left nums[right] nums[right - 1]) right--; while (right left nums[left] nums[left 1]) left; right--; left; }关于这里的去重思路和三数之和的去重一样进行移动去重。while 去重 → 跳过相同数字最后 left /right-- → 移动到新位置继续找下一组解少了最后一步指针不动会死循环结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励