java数据结构与算法刷题-----LeetCode18. 四数之和

本文主要是介绍java数据结构与算法刷题-----LeetCode18. 四数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：`https://blog.csdn.net/grd_java/article/details/123063846`

解题思路

此题为三数之和的衍生题，代码完全一样，只不过多了一层for循环，而多的这一层for循环，也只不过是再复制一份三数之和的for循环罢了

🏆LeetCode15. 三数之和`https://blog.csdn.net/grd_java/article/details/136010556`

思路和三数之和完全一样，先排序。然后枚举数组左边界，作为第一个数
然后因为多了一个数，所以我们使用同样的代码，枚举剩余3个数的左边界，作为第二个数
然后在3个数的左边界，右边区域，使用双指针进行枚举。

代码，时间复杂度O(n^3)，空间复杂度，排序算法使用快速排序，需要O(logN)的栈空间复杂度。

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {//quadruple单词表示 4倍，4重的。quadruplet 表示四组，四套List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();if(nums == null || nums.length < 4) return quadruplets;//排序Arrays.sort(nums);int length = nums.length;//枚举第一个数for(int i = 0; i < length - 3; i++){//因为需要4个数，所以第一个数，最多到倒数第4个数int x = nums[i];//拿到当前遍历的左边界，也就是4个数的第一个数if(i > 0 && x == nums[i-1]) continue;//跳过重复数字，枚举过的，不重复枚举//优化：数组已经排好序（升序），如果x+后面3个数就已经 > 0 了，那当前范围内，最小的3个数都超过目标值，后面的数越来越大，更不行//而且，这一趟都已经超过target了，后面每一趟，就更不行了，所以直接break，不用继续循环了if((long)x + nums[i+1] + nums[i+2] + nums[i+3] > target) break;//优化：如果x+倒数3个数都小于target的话，说明最大的几个数都比目标值小，那么其它的数都比它更小，更无法满足条件了//仅仅这一趟比目标值小，因为x会越来越大，所以后面可能还有满足条件的，所以只是continue跳过这一趟if((long)x + nums[length-1] + nums[length-2] + nums[length-3] < target) continue;//枚举第二个数,下面就是3数之和的代码了for(int j = i+1; j<length-2; j++){int y = nums[j];//拿到当前遍历的三数之和左边界，也就是4个数的第二个数if(j > i+1 && y == nums[j-1]) continue;if((long)x + y + nums[j+1] + nums[j+2] > target) break;if((long)x + y + nums[length-1] + nums[length-2] < target) continue;//双指针枚举另外两个数int left = j + 1, right = length - 1;while(left < right){int z = nums[left], t = nums[right];long sum = (long)x + y + z + t;//4数之和if(sum > target) --right;else if(sum < target) ++ left;else{// quadruplets.add(List.of(x,y,z,t));//下面这行和上面这行效果一样quadruplets.add(Arrays.asList(x,y,z,t));// while(left<right && nums[left]==nums[left+1])left++;// left++;// 下面这句和上面两行效果一样for(++left;left<right && nums[left] == nums[left-1]; ++left);for(--right; right>left && nums[right] == nums[right+1]; --right);}//end_else}//end_while}//end_for}//end_forreturn quadruplets;}//end_method
}//end_class