4SUM LeetCode

思路： 跟3SUM相同，这个时候我为了让代码尽可能简洁，没有搞剪枝，直接就是2重for循环+2SUM。这个时间复杂度为O(n^2)
另外的思路：可以把所有的pair都存到hashmap里，然后做2SUM


public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        HashSet<ArrayList<Integer>> avoidDups = new HashSet<ArrayList<Integer>>();
        if(num.length < 4) return res;
        Arrays.sort(num);
     
        for(int i=0; i<num.length-3; i++){
            for(int j=i+1; j<num.length-2; j++){
                int start = j+1;
                int end = num.length-1;
                while(start<end){
                    if(num[start]+num[end] == target-num[i]-num[j]){ //find one
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    temp.add(num[i]);
                    temp.add(num[j]);
                    temp.add(num[start]);
                    temp.add(num[end]);
                    avoidDups.add(temp);
                    //update index
                    start++;
                    end--;
                    }else if(num[start]+num[end] > target-num[i]-num[j]) end--;
                    else start++;
                 
                }
            }
        }
        res.addAll(avoidDups);
        return res;
    }

public List<List<Integer>> fourSum(int[] num, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Arrays.sort(num);
       
        for (int i=0; i<num.length-3; i++) {
            if (i!=0 && num[i]==num[i-1]) continue;
            for (int j=i+1; j<num.length-2; j++) {
                if (j!=i+1 && num[j]==num[j-1]) continue;
                int start = j+1;
                int end = num.length-1;
                while (start < end) {
                    int runningSum = num[i] + num[j] + num[start] + num[end];
                    if (target < runningSum) {
                        end--;
                    } else if (target > runningSum) {
                        start++;
                    } else {
                        List<Integer> tempList = new ArrayList<Integer>();
                        tempList.add(num[i]);
                        tempList.add(num[j]);
                        tempList.add(num[start]);
                        tempList.add(num[end]);
                        result.add(tempList);
                        start++;
                        end--;
                        while (start < end && num[start] == num[start-1]) start++;
                        while (start < end && num[end] == num[end+1]) end--;
                    }
                }
            }
        }
        return result;
    }