Description:

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

Solutions:

Approach 1: failed with time complexity of O(n^3)

This approach is simple and time cost. It uses 3 loops (i in first loop, j in second loop and k in third loop) to scan the arrays and finds all the combination of 3 elements in the array. If the sum of any of the combinations is zero, the triplets can be added into the list. However, the description requires that the solution cannot contain duplicate triplets. So we have to check if all the triplets are unique. This is another time-costing process.

If we first sort the array and use some tricks, we may well handle the duplicates. However, what I think of is that every time we check in every loop if num[i] == num[i-1], if so, we just let i++. But this doesn't work because, for example, we would get i to 3 if the array is [0, 0, 0, 0].

But we know that the first three elements can form a list that satisfy the condition. What if we just do not check first time in the loop? For example, we would change the if clause to if (i > 0 && i < len-2 && num[i] == num[i-1]) i++, where i would not increase to 3 at the first time. In the same way we change the if clause in the second loop to if (j > 1 && j < len-1 && num[j] == num[j-1]) j++ and in the third loop to if (k > 2 && k < len && num[k] == num[k-1]) k++. However, this doesn't work, either. This is because, for example, if the array is

[-4, -1, -1, 0, 1, 2]

and when i = 1 and j = 2, we know that if k = 5, nums[1] + nums[2] + nums[5] = -1 -1 + 2 = 0. But the algorithm would say: since j = 2 and nums[2] == nums[1], so j++. This would lead j= 3. So the algorithm fails. I haven't think of other good solutions to this issue. So I looked at the discuss and the approach 2 is as followings.

Approach 2: Use 3 pointers with time complexity of O(n^2)

In this approach, we use 3 pointers where the first pointer i just goes from the start to the end and divides the array into the left part and the right part, while the other two named j and k sweep from the right-part array from both of the ends until they meet or cross, which means j = i+1 and k = nums.length-1 at first.
To deal with the duplicate situation, we have 2 steps to go:

• First, we check if nums[i] == nums[i-1], which means we check if the present element is equal to the previous one, if so, we let i++. So in this way, we can guarantee that i always points to a new elements.
• Second, since we let j = i+1 and k = nums.length-1, we always check if nums[j] == nums[j+1] and nums[k] == nums[k-1], if so, we let j++ and k--. So please pay attention that this is different from i case. We check if the present element is equal to the future element but not the previous element.
  The codes are as followings:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < nums.length-2; i++) {
            if (nums[i] > 0) break;
            // if there is several same numbers in the arary, skip to a different one
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int lo = i+1, hi = nums.length-1, target = -nums[i];
            while (lo < hi) {
                if (nums[lo] + nums[hi]  == target) {
                    list.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    while (lo < hi && nums[lo] == nums[lo+1]) lo++;
                    while (lo < hi && nums[hi] == nums[hi-1]) hi--;
                    lo++;
                    hi--;
                } else if (nums[lo] + nums[hi] < target) {
                    lo++;
                } else {
                    hi--;
                }
            }
            
        }
        return list;
    }
}