</br>

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:

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]
]

</br>

Solution

The solution to this problem is to iterate all possible nums[i], nums[j], and then check whether 0-nums[i]-nums[j] is in the array. And to check whether 0-nums[i]-nums[j] is in the array, we can use Array.binarySearch() to return the position of the target number. If the index is above 0, then it means there should be a target answer; and then we can output this array.

Additionally, we have to take care of repetition of the different expression of the actually same array. For example,

[-1,0,1], [-1,1,0], [0,-1,1]...

To solve this, we can first sort three numbers from minimum to maximum, and then store the array into a set. As a Set will get rid of the competition array, in this way, we can output only one expression of the same array.

However, when encountering large number of data, this may result in TLE. Hence, we should skip the unnecessary iteration and improve the efficiency. By adding the following code, we can skip the same number when there's more than two same numbers.

if (i > 1 && nums[i] == nums[i-2]) {              // skip same result
    continue;
}

The code is shown as below.

Java

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        List ans = new ArrayList();
        Set set = new HashSet();
        
        Arrays.sort(nums);
        
        for (int i=0;i<nums.length;i++){
            
            if (i > 1 && nums[i] == nums[i-2]) {              // skip same result
            continue;
            }
            
            for (int j=i+1;j<nums.length;j++){
                int target = 0 - nums[i] - nums[j];
                int index = Arrays.binarySearch(nums, target);
                if(index >= 0 && index != i && index != j){
                    
                    int min = Math.min(nums[i],nums[j]);
                    min = Math.min(min,target);
                    int max = Math.max(nums[i],nums[j]);
                    max = Math.max(max,target);
                    
                    set.add(Arrays.asList(min, 0-min-max, max));
                }
            }
        }
        
        ans.addAll(set);
        return ans;
    }
}

</br>