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.

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)

Thinking:

Sort the array first. Pick a number from the array, and use other two points to record the position of the array and determine which one should change by the sum of them. What’s more, the result set should has no duplicate, so we can use hashset here.

Solution:

public List<List<Integer>> threeSum(int[] nums) {
    int l = nums.length;
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    Set<List<Integer>> tres = new HashSet<List<Integer>>();

    if (l < 3)
        return res;

    Arrays.sort(nums);

    for (int i = 0; i < l-2; i++){
        int k = l-1;
        for (int j = i+1; j < l; j++){
            while (j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0){
                    List<Integer> tempres = new ArrayList<Integer>();
                    tempres.add(nums[i]);
                    tempres.add(nums[j]);
                    tempres.add(nums[k]);
                    tres.add(tempres);
                    while (j < k && nums[j] == tempres.get(1)){
                        j++;
                    }
                    k--;
                }
                else if (sum > 0){
                    k--;
                }
                else{
                    j++;
                }

            }
        }
    }
    res.addAll(tres);

    return res;
}