Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]public class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); List<List<Integer>> res = new LinkedList<>();//保证输出的顺序就是插入的顺序 if(nums == null || nums.length <= 0){ return res; } int max = nums[nums.length - 1]; for (int i = 0; i < nums.length - 3; i++) {//比如：{-4, -1, -1, 0, 1, 5 ,5},最后一次比较的是0,1,5,5 if (4 * nums[0] > target || 4 * max < target) { break; } if (nums[0] + 3 * nums[1] > target || max + 3 * nums[nums.length - 2] < target) { break; } if (4 * nums[i] > target) { break; } if (nums[i] + 3 * max < target) { continue; } if(nums[i]*4 == target){ if(i + 3 < nums.length && nums[i+3] == nums[i]){ res.add(Arrays.asList(nums[i],nums[i],nums[i],nums[i])); } continue; } List<Integer> list; for (int j = i + 1; j < nums.length - 2; j++) { if (j == i + 1 || (j > i + 1 && nums[j] != nums[j - 1])) {//比如-1只能做基准1次，后面的-1直接跳过 int low = j + 1; int high = nums.length - 1;//最后一次num[i] = 0,num[j] = 1,num[lo] = 5,num[hi] = 5 while (low < high) { if (nums[i] + nums[j] + nums[low] + nums[high] == target) { list = Arrays.asList(nums[i], nums[j], nums[low], nums[high]); if (!res.contains(list)) {//去除重复的结果 res.add(list); } while (low < high && nums[low] == nums[low + 1]) low++;//比如：{-4, -1, -1, 0, 1, 5 ,5}，-1只能计算一次，不然会有重复计算 while (low < high && nums[high] == nums[high - 1]) high--;//比如：{-4, -1, -1, 0, 1, 5, 5}，5只能计算一次，不然会有重复计算 low++; high--; } else if (nums[i] + nums[j] + nums[low] + nums[high] < target) { low++; } else high--; }//while }//if }//for }//for return res; }//fourSum }
282 / 282 test cases passed.
Status: Accepted Runtime: 36 ms Your runtime beats 76.98 % of java submissions. T(n) = O(n^3)
方法二：
public class Solution { public List<List<Integer>> fourSum(int[] num, int target) { ArrayList<List<Integer>> ans = new ArrayList<>(); if(num.length<4)return ans; Arrays.sort(num); for(int i=0; i<num.length-3; i++){ if(num[i]+num[i+1]+num[i+2]+num[i+3]>target)break; //first candidate too large, search finished if(num[i]+num[num.length-1]+num[num.length-2]+num[num.length-3]<target)continue; //first candidate too small if(i>0&&num[i]==num[i-1])continue; //prevents duplicate result in ans list for(int j=i+1; j<num.length-2; j++){ if(num[i]+num[j]+num[j+1]+num[j+2]>target)break; //second candidate too large if(num[i]+num[j]+num[num.length-1]+num[num.length-2]<target)continue; //second candidate too small if(j>i+1&&num[j]==num[j-1])continue; //prevents duplicate results in ans list，num[i]不能和num[j]去比较是否相等 int low=j+1, high=num.length-1; while(low<high){ int sum=num[i]+num[j]+num[low]+num[high]; if(sum==target){ ans.add(Arrays.asList(num[i], num[j], num[low], num[high])); while(low<high&&num[low]==num[low+1])low++; //skipping over duplicate on low while(low<high&&num[high]==num[high-1])high--; //skipping over duplicate on high low++; high--; } //move window else if(sum<target)low++; else high--; } } } return ans; } }
282 / 282 test cases passed. Status: Accepted Runtime: 24 ms
Your runtime beats 97.98 % of java submissions.
