15. 3Sum

Return all unique triplets [a, b, c] from nums with a + b + c = 0. The result must not contain duplicate triplets.

Sort, fix nums[i], then move lo and hi inward on the rest: a small sum moves lo right, a big sum moves hi left. Skip equal values to avoid duplicates.

1function threeSum(nums: number[]): number[][] {
2  nums.sort((a, b) => a - b);
3  const res: number[][] = [];
4  for (let i = 0; i < nums.length - 2; i++) {
5    if (nums[i] > 0) break;
6    if (i > 0 && nums[i] === nums[i - 1]) continue;
7    let lo = i + 1, hi = nums.length - 1;
8    while (lo < hi) {
9      const sum = nums[i] + nums[lo] + nums[hi];
10      if (sum < 0) lo++;
11      else if (sum > 0) hi--;
12      else {
13        res.push([nums[i], nums[lo], nums[hi]]);
14        while (lo < hi && nums[lo] === nums[lo + 1]) lo++;
15        while (lo < hi && nums[hi] === nums[hi - 1]) hi--;
16        lo++; hi--;
17      }
18    }
19  }
20  return res;
21}

nums (sorted)

-4

-1

result

empty

Sort nums.

1 / 0

Space: play/pause · ←/→: step