LeetCode184-Sum

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;
}