4Sum

 Q：
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:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ? b ? c ? d)
• 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) 

A：
 ---------------4th pass--------------------------------------
思路很简单，就是把4 sum 换成3 sum，然后加入即可。

public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        List<List<Integer>> all = new LinkedList<List<Integer>>();
        Arrays.sort(num);
        if(num==null || num.length<4)
            return all;
        for(int i =0;i<num.length-3;i++){
            if(i!=0 && num[i] == num[i-1])// unique for the first element
                continue;
            List<List<Integer>> subAll = threeSum(num,i+1,target-num[i]);
            for(List<Integer> al : subAll)
                al.add(0,num[i]);
            all.addAll(subAll);
        }
        return all;
    }
    private List<List<Integer>> threeSum(int[] num, int start, int target) {
        List<List<Integer>> all = new LinkedList<List<Integer>>();
        for(int i1 = start;i1<num.length-2;i1++){
            if(i1!=start && num[i1] == num[i1-1])
                continue;
            int i2 = i1+1,i3=num.length-1;
            while(i2<i3){
                while(i3-1>i2 && num[i1]+num[i2]+num[i3]>target)
                    i3--;
                if(num[i1]+num[i2]+num[i3] == target){
                    List<Integer> al = new LinkedList<Integer>();
                    al.add(num[i1]);
                    al.add(num[i2]);
                    al.add(num[i3]);
                    all.add(al);
                }
                // update i2 to a new value
                while(i2+1<i3 && num[i2] == num[i2+1])
                    i2++;
                i2++;
            }
        }
        return all;
    }
}

Mistakes：
这里，忘了update i2 into a new value,


--------------------1st pass ----------------------
Idea: partition the p1, p2, p3, p4 into two groups,
p1 with p4 as the outer round(但这个不是linear的， 哎，原以为一定是linear的， 总共也是O(n^2)的，所以白花了好几个小时。

and p2 with p3 as the inner round.

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> all = new LinkedList<List<Integer>>();
        Arrays.sort(nums);
        for(int i0=0;i0 < nums.length -3;i0++){
            if(i0>0 && nums[i0] == nums[i0-1])
                continue;
            for(int i2=i0+1;i2<nums.length-2;i2++){
                if(i2>i0+1 && nums[i2] == nums[i2-1])
                    continue;
                int j = i2+1, k = nums.length-1;
                while(j<k){
                    if(nums[i0] + nums[i2] + nums[j] + nums[k] == target){
                        List<Integer> al = new LinkedList<Integer>();
                        al.add(nums[i0]);
                        al.add(nums[i2]);
                        al.add(nums[j]);
                        al.add(nums[k]);
                        all.add(al);
                    }
                    while(j< k &&  nums[i0] + nums[i2] + nums[j] + nums[k] == target )
                        j++;
                    if(j< k &&  nums[i0] + nums[i2] + nums[j] + nums[k] < target)
                        j++;
                    else
                        k--;
                }
            }
        }
        return all;
        
    }
}

Mistakes:
1； 光顾得上p1,p4不要重复了，忘了把p2,p3也不能重复
2： 光想到，对想同的p1,  先只考虑最后一个p1的值。了，。但是这样，就导致了，相同的值，不能作为p2了。应该是先把读取，然后，再移动到下一个不同的index上。
 哎～～～～～头脑还是不够清晰阿
3: 哎， 如果target 是0， 那【....0，0，0，0....]也行的阿。 你这么跳，就不行了。 所以说，4sum不能像2sum那么跳。
哎～～～～～～～～～～～～～～～～～～ SB Tiger
4:  inner circle 中，（就是对于p2 , p3 的twoSum()方法里， 应该是p3>p2+1的时候，才是p3--;  否则，仅仅是p3>p2, 就会导致p3==p2

-------------------------------------第二遍---------------------想加速，就先把所有的potentiao sum value 都计算了，然后，记录下了要增加达到他们的地址。-------------可是，这样，对于重复的问题，就很难办， 比较讨厌。 还是不用这个方法了。。  乖乖地用O(n^3)的方法吧。


5：   2 pointer的时候，在第二个while里面，不要忘记判断下标越界。

6:  do {} while() 后面要加分号 ;
7:  第一个while中，应该是while(p0+3 <= p3) ,而不是简单的小于
8：  when updating p1, we originally wrote
    // update p0 to a different value
            do {
                p0++;
            } while (p0 + 3 <= p3 && num[p0] == num[p0 + 1]);
Which is wrong,     因为先加再对比，会出现这样的情况：例如，p1 =1,  num = [ -2, -1, 0 , 0 , 3]  运行完上面这句，  p1就变成 指向最后那个0 了
应该是
while (p1 < p2 && num[p1] == num[p1 + 1]){
                    p1++;
                };
                p1++;

9：这次写，没有update p3指针， 哎， 就是最右边的那个指针啦。
  还是像第一次那样，extract出一个子函数吧。 哎，~~~~丢人。 本以为很easy，可以一次pass的呢
10 ： 第一遍的时候， p4=n-1 是在update p1之前。可是。这次，是在第一个while之后，因此，这样的话，每次要对比的，就是p0+3<n 的样子了。

-----------------------------第三遍--------------------------方法同上，  ----------
Mistakes:
1:  慎用 do {} while 语句。
例如， findMatch()中，要更新 i的位置(其实就是i2）
            do{
                i++;// avoid duplicates of j
            }while( i < j && num[i + 1] == num[i]) ;
这样是不对的。  因为，这样，首先更新了i的位置，再对比，就不再是 原有的i值的对比了。