15. 3Sum

3Sum is really 2Sum on a sorted array, done n times. Fix one element a; then find pairs (b, c) in the remaining array with b + c == -a. On a sorted array that pair search is O(n) with two pointers.

Approach

1. Sort nums.
2. For each i from 0 to n-3:
   • Skip if nums[i] == nums[i-1] (dedupe the fixed element).
   • Set l = i + 1, r = n - 1.
   • While l < r:
     • If nums[i] + nums[l] + nums[r] == 0, record it, then advance l and retreat r, skipping duplicates.
     • If the sum is < 0, move l right (need larger).
     • If > 0, move r left (need smaller).

Why sorting helps

Sorting lets us deduplicate in O(1) (neighbors are equal) and gives us a monotonic sum as we move pointers inward, so we never miss a triplet.

Complexity

• Time: O(n log n) + O(n²) = O(n²).
• Space: O(1) extra (ignoring sort stack / output).

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = n - 1;
            while (l < r) {
                int s = nums[i] + nums[l] + nums[r];
                if (s == 0) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    l++;
                    r--;
                    while (l < r && nums[l] == nums[l - 1]) l++;
                    while (l < r && nums[r] == nums[r + 1]) r--;
                } else if (s < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return res;
    }
}