LeetCode 18.四数之和

1.思路：和hot100 15.三数之和一样，先排序。排序后，枚举nums[i]作为第一个数，枚举nums[j]作为第二个数，那么问题就变成找到另外两个数，使得这四个数的和等于target，这可以用双指针解决。

2.优化思路：

对于nums[i]的枚举：

（1）设s = nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3]。由于数组已经排序，如果s > target，后面无论怎么选，选出的四个数之和都不会比s还小，所以后面不会找到等于target的四数之和了。所以只要s > target，就可以直接break外层循环了。

（2）设s = nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3]。由于数组已经排序，如果s < target，nums[i]加上后面的任意三个数都不会超过s了，所以无法在后面找到另外三个数与nums[i]相加等于target。但是nums[i]可以继续往后找更大的nums[i]，还是可能会出现四数之和等于target的情况的，所以还需要继续枚举，continue外层循环。

（3）如果i > 0且nums[i] = nums[i - 1]，那么nums[i]和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接continue外层循环（可以放在循环开头判断）。

对于nums[j]的枚举（j从i + 1开始），也同样有类似的优化：

（1）设s = nums[i] + nums[j] + nums[j + 1] + nums[j + 2]。由于数组已经排序，如果s > target，后面无论怎么选，选出的四个数之和都不会比s还小，所以后面不会找到等于target的四数之和了。所以只要s > target，就可以直接break了。

（2）设s = nums[i] + nums[j] + nums[n - 1] + nums[n - 2]。由于数组已经排序，如果s < target，nums[i]加上nums[j]再加上后面任意两个数都不会超过s了，所以无法在后面找到另外两个数与nums[i]和nums[j]相加等于target。但是nums[j]可以继续往后找更大的nums[j]，还是可能会出现四数之和等于target的情况的，所以还需要继续枚举，continue。

（3）如果j > i + 1且nums[j] = nums[j - 1]，那么nums[j]和后面数字相加的结果，必然在之前算出过，所以无需执行后续代码，直接continue（可以放在循环开头判断）。注意这里的j > i + 1的判断是必须的，如果不判断，对于示例2这样的数据，会直接continue，漏掉符合要求的答案。

3.复杂度分析：

（1）时间复杂度：O(n^3)，其中n为nums的长度。排序O(nlogn)。两重循环枚举第一个数和第二个数，然后O(n)双指针枚举第三个数和第四个数。所以总的时间复杂度为O(n^3)。

（2）空间复杂度：O(1)。忽略返回值和排序的栈开销，仅用到若干变量。

附代码：

class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); int n = nums.length; for(int i = 0;i < n - 3;i++){ // 枚举第1个数 // 使用long避免溢出 long x = nums[i]; if(i > 0 && x == nums[i - 1]){ // 跳过重复数字 continue; } // 这里四数之和有可能是long范围 // 由于x设置为了long类型，数组元素在参与运算时也会自动升级为long运算，避免了溢出 if(x + nums[i + 1] + nums[i + 2] + nums[i + 3] > target){ // 优化1 break; } // 这里四数之和有可能是long范围 // 由于x设置为了long类型，数组元素在参与运算时也会自动升级为long运算，避免了溢出 if(x + nums[n - 3] + nums[n - 2] + nums[n - 1] < target){ // 优化2 continue; } for(int j = i + 1;j < n - 2;j++){ // 枚举第2个数 // 使用long避免溢出 long y = nums[j]; if(j > i + 1 && y == nums[j - 1]){ // 跳过重复数字 continue; } // 这里四数之和有可能是long范围 // 由于x和y设置为了long类型，数组元素在参与运算时也会自动升级为long运算，避免了溢出 if(x + y + nums[j + 1] + nums[j + 2] > target){ // 优化1 break; } // 这里四数之和有可能是long范围 // 由于x和y设置为了long类型，数组元素在参与运算时也会自动升级为long运算，避免了溢出 if(x + y + nums[n - 2] + nums[n - 1] < target){ // 优化2 continue; } int k = j + 1; int l = n - 1; // 双指针枚举第3个数和第4个数 while(k < l){ long sum = x + y + nums[k] + nums[l]; if(sum > target){ l--; }else if(sum < target){ k++; }else{ // 四数之和等于target // 由于x和y定义为了long类型，但res定义为了List<Integer>类型。而非List<Long>类型 // x和y为long型会导致所有参数都升级为long类型 // 因此需要先强制把x和y转换为int类型 res.add(List.of((int) x,(int) y,nums[k],nums[l])); k++; l--; // 数组已排序，相同的数字会相邻，需跳过重复数字 // 跳过重复数字 while(k < l && nums[k] == nums[k - 1]){ k++; } // 跳过重复数字 while(k < l && nums[l] == nums[l + 1]){ l--; } } } } } return res; } }

ACM模式：

import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n - 3; i++) { long x = nums[i]; if (i > 0 && x == nums[i - 1]) { continue; } if (x + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) { break; } if (x + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) { continue; } for (int j = i + 1; j < n - 2; j++) { long y = nums[j]; if (j > i + 1 && y == nums[j - 1]) { continue; } if (x + y + nums[j + 1] + nums[j + 2] > target) { break; } if (x + y + nums[n - 2] + nums[n - 1] < target) { continue; } int k = j + 1; int l = n - 1; while (k < l) { long sum = x + y + nums[k] + nums[l]; if (sum > target) { l--; } else if (sum < target) { k++; } else { res.add(List.of((int) x, (int) y, nums[k], nums[l])); k++; l--; while (k < l && nums[k] == nums[k - 1]) { k++; } while (k < l && nums[l] == nums[l + 1]) { l--; } } } } } return res; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取数组长度 int n = scanner.nextInt(); // 读取数组元素 int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } // 读取目标值 int target = scanner.nextInt(); // 计算四数之和 Solution solution = new Solution(); List<List<Integer>> result = solution.fourSum(nums, target); // 输出结果：每个四元组占一行，数字之间用空格分隔 for (List<Integer> list : result) { for (int j = 0; j < list.size(); j++) { System.out.print(list.get(j)); if (j < list.size() - 1) { System.out.print(" "); } } System.out.println(); } scanner.close(); } }