[LeetCode]18.4 Sum

第一思路想到的是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;
}