LeetCode 15 · Medium · Two Pointers

3Sum

Given an integer array nums, list every distinct triplet of values from three different positions that adds up to zero. The same triplet of values must not appear twice in the answer.

O(n²)time
O(1)extra space · besides sorting
sort + 2 ptrsfix a, then Two Sum II

3–12 integers, −20 to 20

0

res blue = fixed a · outline = nums[l..r], the Two Sum II search for −a

public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { int a = nums[i]; if (a > 0) { break; // all that is left is positive } if (i > 0 && a == nums[i - 1]) { continue; // same a, same triplets } int l = i + 1; int r = nums.length - 1; while (l < r) { int s = a + nums[l] + nums[r]; if (s > 0) { r--; } else if (s < 0) { l++; } else { res.add(Arrays.asList(a, nums[l], nums[r])); l++; r--; while (l < r && nums[l] == nums[l - 1]) { l++; } } } } return res;}
i, a
—
l
—
r
—
s
—
res
[]

Why it works

  1. Brute force tries every triple: O(n³), plus a set of sorted triplets to drop repeats.
  2. Fix one, two-pointer the rest. After sorting, fix a = nums[i] and look for a pair in nums[i+1..n-1] that sums to −a. That is Two Sum II: too big drops r, too small drops l, and the outline only shrinks.
  3. Why O(n²): n choices of a, each with one O(n) pointer sweep. Sorting's O(n log n) is smaller. No hash set is needed for uniqueness.
  4. Pitfall, duplicates: skip an a equal to the previous one, and after a hit move l past copies of the value just used. Otherwise [-2,0,0,2,2] reports [-2,0,2] twice.
  5. Early exit: once a > 0, every value to its right is positive too, so no triplet can reach 0.
  6. Follow-up: 4Sum adds one more fixed loop around the same sweep, O(n³).