[LeetCode] 3 sum

Question:

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.

解题思路：2个pointer，前后扫描。注意移动的时候，要移到下一个不同的数。

Java Code:

public List> threeSum(int[] num) {
        Arrays.sort(num);
        List> res = new ArrayList>();
        
        for(int i = 0; i < num.length - 2;){
            int s = i+1;
            int e = num.length - 1;
            
            while(s < e){
                int total = num[i]+num[s]+num[e];
                if(total == 0){
                    List tmp = new ArrayList();
                    tmp.add(num[i]);
                    tmp.add(num[s]);
                    tmp.add(num[e]);
                    res.add(tmp);
                }
                
                if(total >= 0){
                    e--;
                    while(e > s && num[e+1] == num[e]) e--;
                }
                
                if(total <= 0){
                   s++;
                   while(e > s && num[s] == num[s-1]) s++;
                }
            }
            
            i++;
            while(i < num.length-2 && num[i] == num[i-1]) i++;
        }
        
        return res;
}