Three SUM LeetCode

3SUM
思路： 运用2SUM中的第二个方法，唯一需要注意的地方就是防止重复的结果出现。
比如 数组 {1, 1, 1, 2, 3, 4} target 6
这样我们实际上只有一组答案，就是{1, 1, 2} 另外一组跟这个组是一模一样的所以跳过。

具体看代码。
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {

        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(num.length < 3) return res;
        Arrays.sort(num);
        for(int i=0; i<num.length - 2 && num[i]<=0; i++){
        //num[i]<= 0适当的减少了一定量的计算，如果想不到应该也没关系
            if(i>0 && num[i]==num[i-1]) continue; //防止duplicate
            int start = i + 1;
            int end = num.length - 1;
            while(start < end){
                int runningSum = num[i] + num[start] + num[end];
                if (runningSum > 0) end--;
                else if(runningSum < 0) start++;
                else{//find one solution and save it to the arraylist
                ArrayList<Integer> temp = new ArrayList<Integer>();
                temp.add(num[i]);
                temp.add(num[start]);
                temp.add(num[end]);
                res.add(temp);
             
                //update start and end
                start++;
                end--;
                //skip the duplicates
                while(start<end && num[start]==num[start - 1]) start++;
                while(start<end && num[end] == num[end + 1]) end--;
                }
            }
        }
        return res;
    }

Updating version:
public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
if (num == null || num.length < 3) return result;
Arrays.sort(num);

for (int i=0; i<num.length-2 &&num[i] <= 0; i++) {
//avoid duplicate for the first elements
if (i>0 && num[i]==num[i-1]) continue;
int start = i + 1;
int end = num.length - 1;
while (start < end) {
int runningSum = num[i] + num[start] + num[end];
//DO 2SUM searching
if (runningSum >0) {
end--;
} else if (runningSum < 0) {
start++;
} else {
List<Integer> temp = new ArrayList<Integer>();
temp.add(num[i]);
temp.add(num[start]);
temp.add(num[end]);
result.add(temp);

//updating the index to avoid the duplicate for 2nd and 3rd elements
start++;
end--;
while (start < end && num[start] == num[start-1]) start++;
while (start < end && num[end] == num[end + 1]) end--;
}
}

}
return result;  
    }