3Sum | Leetcode

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)

---

Solution: Sort the input array. Iterate through the array. For each element i, find the 2Sum of elements i+1 to the end of the array such that nums[i] + nums[j] + nums[k] == 0, or -nums[i] = nums[j] + nums[k]. For each 2Sum, start from the two ends of the subarray. If the current number is too small, make it bigger by advancing from the left end. If too big, make it smaller by advancing from the right end. Check for duplicate solutions by skipping duplicate numbers.

public class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        // If we need to preserve input, just clone into new array.
        Arrays.sort(nums);
        
        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            int n = nums[i];
            
            // Avoid duplicate solutions.
            if (i > 0 && n == nums[i - 1]) continue;
            
            int start = i + 1;
            int end = nums.length - 1;
            
            while (start < end) {
                int first = nums[start];
                int last = nums[end];
                
                if (first + last == -n) {
                    answer.add(Arrays.asList(n, first, last));
                    start++;
                    end--;
                    
                    // Avoid duplicate solutions.
                    while (start < end && nums[end] == last) end--;
                    while (start < end && nums[start] == first) start++;
                } else if (first + last < -n) {
                    // Current sum is too small, so make it bigger.
                    start++;
                } else {
                    // Current sum is too big, so make it smaller.
                    end--;
                }
            }
        }
        
        return answer;
    }
}