Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
    }
}

Problem Clarification

Each pair of triplets in the solution must differ in at least one element.

Idea – 1

We first sort the array to facilitate comparing two triplets to see if they are unique. So, all triplets we would generate would be sorted as well, which is fine. Now, consider a triplet . If then we have . Thus if two triplets has the same any two elements then the triplets are not unique. We need to ensure that two triplets either have different a’s or different b’s. If we ensure the following two conditions, we would collect all unique solutions: 1. We batch all triplets that have a as the first element but have different b’s. All elements in such a batch thus differ in b and would be considered as unique solutions. 2. After step 1, we now move onto a different a (never considering the a in an earlier batch) and repeat step 1. We would not miss a solution, because for each solution triplet, the first of its three elements (in sorted order) must be in one of the batches – since we consider each distinct element as the first element in some batch. For that batch, we have considered all distinct elements that come after a (in sorted order) as the second element. Given two elements the third element is uniquely determined. The algorithm has time complexity and space complexity.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> sol = new ArrayList<>();
        int n = nums.length;
        if(n < 3)
        {
            return sol;
        }
        
        Arrays.sort(nums);
        
        for(int i = 0; i < n-2; ++i)
        {
            // make sure two batches differ in first element
            if(i > 0 && nums[i-1]==nums[i])
            {
                continue;
            }
            
            int j = i+1, k = n-1;
            while(j < k)
            {
                // make sure in a batch, two triplets differ in the second element
                if(j > i+1 && nums[j-1]==nums[j])
                {
                    ++j;
                }
                else
                {
                    int sum = nums[i]+nums[j]+nums[k];
                    if(sum == 0)
                    {
                        sol.add(Arrays.asList(nums[i], nums[j], nums[k]));
                        ++j;
                        --k;
                    }
                    else if(sum < 0) // increase sum
                    {
                        ++j;
                    }
                    else // decrease sum
                    {
                        --k;
                    }
                }
            }
        }
        
        return sol;
    }
}

Runtime: 38 ms, faster than 72.31% of Java online submissions for 3Sum.
Memory Usage: 49.6 MB, less than 36.09% of Java online submissions for 3Sum.