leetcode 3sum

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)


使用两个标记，left和right， 对于每一个值，分别从左向右，从右向左计算

！！   如何消除duplicate 不太会！！！

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
    	if(num==null||num.length<3){
    		return result;
    	}
    	
    	int sum=0;
    	Arrays.sort(num);
        for(int i=0;i<num.length-2;i++){
            if (i != 0 && num[i] == num[i - 1]) {
				continue; // to skip duplicate numbers; e.g [0,0,0,0]
			}
        	int left=i+1;
        	int right=num.length-1;
        	while(left<right){
        		sum=num[i]+num[left]+num[right];
        		if(sum==0){
        			ArrayList<Integer> temp=new ArrayList<Integer>();
        			temp.add(num[i]);
        			temp.add(num[left]);
        			temp.add(num[right]);
        			result.add(temp);
        			left++;
        			right--;
        			while (left < right && num[left] == num[left - 1]) { // to skip duplicates
						left++;
					}
					while (left < right && num[right] == num[right + 1]) { // to skip duplicates
						right--;
					}
        		}
        		else if(sum<0){
        			left++;
        		}
        		else{
        			right--;
        		}
        	}
        }
        
        return result;
    }
}