3Sum

Q:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a <= b <= c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

A:

即使是用先把两个加起来，然后，再找第三个的方式，复杂度也是O(n^2)阿。
还有更简单的吗？
----------------第一遍自己写的，写了100多行， 比较SB，就删掉了，反正也不会再看---------
--------这是第三遍-----------------------

public class threeSome { 
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> all = new LinkedList<List<Integer>>();
        if(num == null || num.length <3)
            return all;
        Arrays.sort(num);
        int n = num.length;
        for(int i=0;i<n-2;i++){
            if(i!=0 && num[i] == num[i-1])
                continue;
            int j=i+1, k = n-1;
            while(j<k){
                while(j<k && num[i]+num[j]+num[k] >0)
                    k--;
                if( j<k && num[i]+num[j]+num[k] == 0 ){
                    List<Integer> al = new LinkedList<Integer>();
                    al.add(num[i]);
                    al.add(num[j]);
                    al.add(num[k]);
                    all.add(al);
                }
                while(j<k && num[j+1]==num[j])
                    j++;
                j++;
            }
        }
        return all;
    }
} 

声明List of List时，new 后面的语句中，第一层<>里面的不能写成LinkedList的
Mistakes:

1 : 

if (num[k] < 0)
      continue;

这里，本来写的是，当num[k]<0的时候，是继续往下跑，而不是跳出，的
哎，还是对break, continue的理解不够深啊。---- 对自己的算法，也是理解不够清楚。
2:其实对于unique2方法，可以不用考虑三个0的情况，就只允许最多三个重复的就行。记得到最后检测重复即可。
所谓的two Pointer 算法。
Given two arrays (A and B) sorted in ascending order, and an integer x. we need to find i and j, such that a[i] + b[j] is equal to X. i and j our pointers, at first step i is points to the first element of a, and j points to the last element of b. i = 0; j = b.size() - 1; move first pointer one by one through the array a, and correct position of the second pointer if needed while (i < a.size()) { while(a[i] + b[j] > X && j > 0) j--; if (a[i] + b[j] == X) writeAnswer(i, j); i++; } Also, there was the same question in Russian, maybe it can helps. link to google-translated version http://codeforces.ru/blog/entry/4136
下面这个SB方法，就是简单地遍历所有的可能，先排序，然后3个runner都从前往后跑，第一个必须<0 >0 然后加入时，和刚刚加入的，对比，如果一样，就不加。否则加入到结果里。

---------------------第三遍的代码，精简了些---------------- Idea: o(n^2) solution exists. First sort the array, and then from left to right, for each num[i], search the pair that sums up to -num[i] using Two Sum algorithm.

public class Solution {
      public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> al;
        int n = num.length;
        Arrays.sort(num);    
        for(int first =0;first<n-2;first++) {
            int target = -num[first];
            // then following is the 2 sum
            int i = first + 1;
            int j = n - 1;
            while (i < j) {
                while (i < j && num[i] + num[j] >= target) {
                    if (num[i] + num[j] == target) {
                        al = new ArrayList<Integer>();
                        al.add(num[first]);
                        al.add(num[i]);
                        al.add(num[j]);
                        if( all.isEmpty() )
                            all.add(al);
                        else{
                            ArrayList<Integer> preList = all.get(all.size()-1);
                            if(preList.get(1) != al.get(1) || preList.get(2)!=al.get(2)){
                                all.add(al);
                            }
                        }
                    }
                    j--;
                }
                i++;
            }
            while(first+1<n-2 && num[first+1] == num[first])
                first++;
        }
        return all;
    }
}

---------------- we do not need the repeat of  "first" value at all. ---------------------------
Then by checking the last two elements is not equal, we guarantee no duplicate.



-------------------------第二遍--------------对a进行遍历的时候，分开处理3个a全等， 2个a相等和 只有1个a的情况（这时候，需要用到2sum）

public class Solution {
      public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        boolean threeZero = false; // if we find a=b=c=0
        for (int i = 0; i < num.length - 2; i++) {
            // test the case that 3 A[i] in a row and they are all == 0
            if (num[i] == num[i + 1] && num[i] == num[i + 2]) {//
                if (num[i] == 0)
                    threeZero = true;
                continue;
            }
            // now deal with the case that two value of num[i]
            if (num[i] == num[i + 1]) {
                for (int j = i + 2; j < num.length; j++)
                    if (num[i] + num[i + 1] + num[j] == 0) {
                        add2All(num[i], num[i + 1], num[j], all);
                        break;
                    }
                continue;
            }
            // Now, num[i] is the only appearance,we can use two pointer
            // algorithm
            twoSum(num, i + 1, -num[i], all); // two sum ,by adding num[i] back
        }
        if (threeZero) {
            add2All(0, 0, 0, all);
        }
        return all;
    }

    ArrayList<ArrayList<Integer>> twoSum(int[] num, int begin, int target,
            ArrayList<ArrayList<Integer>> all) {
        // NOTE: num is already sorted
        int i = begin, j = num.length - 1;
        while (i < j) {
            // update i so that num[newI] is the last appearance of num[i]
            boolean flag = false; // whether num[i] is half of target
            while (i < j && num[i + 1] == num[i]) {
                if (num[i] + num[i + 1] == target) {
                    flag = true;
                }
                i++;
            }
            if (flag)// if we have num = 0 , 2,2,3, begin == 1, target = 4
                add2All(-target, num[i - 1], num[i], all);

            while (j > i && num[i] + num[j] >= target) {
                if (num[i] + num[j] == target) {
                    add2All(-target, num[i], num[j], all);
                    break;
                }
                j--;
            }
            i++; // update i to the next
        }
        return all;
    }

    void add2All(int a, int b, int c, ArrayList<ArrayList<Integer>> all) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        al.add(a);
        al.add(b);
        al.add(c);
        all.add(al);
    }
}