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 targetnums[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 targetnums[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 ListListInteger fourSum(int[] nums, int target) { Arrays.sort(nums); ListListInteger 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定义为了ListInteger类型。而非ListLong类型 // 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 ListListInteger fourSum(int[] nums, int target) { Arrays.sort(nums); ListListInteger 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(); ListListInteger result solution.fourSum(nums, target); // 输出结果每个四元组占一行数字之间用空格分隔 for (ListInteger 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(); } }