四数之和 Posted on 2021-07-17 00:00:00 2021-07-17 00:00:00 by Author 摘要 三数之和已经解决了,那么又怎么解决四数之和尼????? # 四数之和 1. 题目描述:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。(与三数之和不同的是,这里的目标值不是0,而是target) 2. 示例描述: - 示例一: - 输入: nums = [1, 0, -1, 0, -2, 2],target = 0。 - 输出: [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] - 解释:-1+1+0+0 = 0(target),-2+0+0+2 =0(target) - 示例二: - 输入: nums = [3, 0, 2, 0, -2, -1],target = 0。 - 输出:[3, 0, -2 ,-1], [2, 0, -2, 0] - 解释:3+ 0+ (-2+ +(-1) =0(target),-2+0+2+0 =0(target) 3. 解题思路:本题和三数之和类似,只不过就是target改变为想要输入的值了。然后就在三数之和上面在套一层循环,然后就固定死了两个值,之后就和求三数之和的实现逻辑类似。所以看本篇文章之前,建议先看三数之和,里面有详细解释,想看三数之和的blog请移步这篇文章:[三数之和](http://jianshu.com)。 具体实现细节以及逻辑,见如下代码,每一步都有详细的解释。 4. 代码实现: ```java public List<List<Integer>> fourSum(int[] nums, int target) { //定义结果集合 List<List<Integer>> result = new ArrayList<>(); //首先对数组进行排序,这是前提,因为使用双指针解决这个问题,前提是数组有序的 Arrays.sort(nums); //第一层循环,用来固定第一个值 for (int i = 0; i < nums.length; i++) { //这里是去重的步骤。 //解释为什么这样做可以去重:因为数组有序,题目要求返回的结果集中不能有重复的结果 //用反证法可以,有多个相同的数,与其他不同的3个数相加结果为target, //那这相同的多个数分别与不同于这个数的三个数结合,就为多个相同的结果集。就有重复的结果,不满足题意 //文字太抽象,直接上栗子[-1,0,0,1,1,1],target=0,这里有三个相同的1,这三个相同的1与-1,0,0的和为0, //如果不去重,就会得到3个相同的结果集,就重复了,不满足题目要求 if (i > 0 && nums[i] == nums[i - 1]) { continue; } //第二层循环,用来固定第二个值 for (int k = i + 1; k < nums.length; k++) { //同样也是去重 if (k > i + 1 && nums[k] == nums[k - 1]) { continue; } //下面的步骤与三数之和的逻辑相同,唯一不同的就是三数之和为三个数相加的和为0, //而本题是四个数之和为target,但是具体逻辑都相同 int left = k + 1; int right = nums.length - 1; //开始left指针和right指针的表演,计算当前和,如果等于目标值,left++并去重,right--并去重, //如果当前和大于目标值时right--,如果当前和小于目标值时left++ while (left < right) { //如果四个数的和小了,那么left需要右移动(数组从小到大排序) //如果四个数的和大了,那么right需要左移动(数组从小到大排序) if (nums[i] + nums[k] + nums[left] + nums[right] > target) right--; if (nums[i] + nums[k] + nums[left] + nums[right] < target) left++; //如果四数之和等于target,就假如结果集中 else if (nums[i] + nums[k] + nums[left] + nums[right] == target) { List<Integer> temp = new ArrayList<>(); temp.add(nums[i]); temp.add(nums[k]); temp.add(nums[left]); temp.add(nums[right]); result.add(temp); //这两步也是去重 while (right > left && nums[right - 1] == nums[right]) right--; while (right > left && nums[left] == nums[left + 1]) left++; //去重完了之后,为什么right--,left++ //因为上一步已经把结果集加入最终结果集合中,所以 //需要继续寻找下一个满足条件的结果集 right--; left++; } } } } //返回最终的结果 return result; } ```
{{ item.content }}
{{ child.content }}