Problem

3Sum

LeetCode #15Medium
Find all unique triplets that sum to zero

Given an integer array, find all unique triplets that sum to zero, with no duplicate triplets in the result.

Asked atAmazonMetaGoogleMicrosoft
-4
-1
-1
0
1
2
[0][1][2][3][4][5]
Brute force
▸
1given arr
2for i ← 0 to n − 3:
3    for j ← i + 1 to n − 2:
4        for k ← j + 1 to n − 1:
5            if arr[i] + arr[j] + arr[k] == 0:
6                record (i, j, k)
7dedupe results   // needs a set → O(n) extra space
state
  • target0
  • n6

line 1Find every unique triplet (a, b, c) in arr with a + b + c = 0.