Given an array nums of n integers and an integer target, are there
elements a, b, c, and d in nums 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.
Example:
Given array nums = [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] ]
第一思路想到的是HashMap 保存两组两个的数据，进行匹配，构建map的消耗是o(n^2),遍历的消耗是o(n^2),寻找target并构建是常量级，复杂度应该是n^2,但最后的性能数据并不理想，没太想明白，可能是数据量不够
public List<List<Integer>> fourSum(int[] nums, int target) { Arrays.sort(nums); List<List<Integer>> ret=new ArrayList(); HashMap<Integer,List<int[]>> map1=new HashMap(); HashMap<Integer,List<int[]>> map2=new HashMap(); for(int i=0;i<nums.length-1;i++){ if(i>0 && nums[i]==nums[i-1]) continue; for(int j=i+1;j<nums.length;j++){ if(j>i+1 && nums[j]==nums[j-1]) continue; if(!map1.containsKey(nums[i]+nums[j])) map1.put(nums[i]+nums[j],new ArrayList()); map1.get(nums[i]+nums[j]).add(new int[]{i,j}); } } for(int i=nums.length-1;i>=1;i--){ if(i<nums.length-1 && nums[i]==nums[i+1]) continue; for(int j=i-1;j>=0;j--){ if(j<i-1 && nums[j]==nums[j+1]) continue; if(!map2.containsKey(nums[i]+nums[j])) map2.put(nums[i]+nums[j],new ArrayList()); map2.get(nums[i]+nums[j]).add(new int[]{j,i}); } } for(int key:map1.keySet()){ if(!map2.containsKey(target-key)) continue; for(int[] i:map1.get(key)){ for(int[] j:map2.get(target-key)){ if(i[1]>=j[0]) continue; ret.add(Arrays.asList(nums[i[0]],nums[i[1]],nums[j[0]],nums[j[1]])); } } } return ret;}常规写法就是在上一题的基础上，加一层循环
public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> ret=new ArrayList(); Arrays.sort(nums); for(int i=0;i<nums.length-3;i++){ if(i>0 && nums[i]==nums[i-1]) continue; for(int j=i+1;j<nums.length-2;j++){ if(j>i+1 && nums[j]==nums[j-1]) continue; int two=nums[i]+nums[j]; int left=j+1; int right=nums.length-1; while(right>left){ if(left>j+1 && nums[left]==nums[left-1]) { left++; continue; } if(right<nums.length-1 && nums[right]==nums[right+1]) { right--; continue; } if(two+nums[left]+nums[right]==target) ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right])); if(two+nums[left]+nums[right]<=target) left++; else right--; } } } return ret;}