3Sum
Find every distinct triple of values whose sum is zero. A triple must use three distinct positions. Sort each triple and print the triples in lexicographic order.
Work through the cases
3 examplesInput notation
Space-separated integers on line 1.Expected result
One space-separated triple per line, or none.Case 1
Input
-2 0 2 1 -1
Expected output
-2 0 2 -1 0 1
Case 2
Input
1 2 3
Expected output
none
Case 3
Input
0 0 0 0
Expected output
0 0 0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The first idea is three nested loops plus a set for uniqueness. Correct, but O(n^3). n ≤ 3000 will not pass. Hashing two-sum for each i reaches O(n^2), yet duplicates and extra space are messy. The bottleneck is finding two numbers that sum to the opposite of a fixed value, without repeating triplets. Sort first so duplicates sit together and are easy to skip; two-sum on a sorted array is two pointers in O(n). If nums[i]>0, everything after it is positive, so the sum cannot be 0 anymore. So we sort, enumerate the first number, and squeeze the rest with two pointers.
We notice that the problem does not require us to return the triplet in order, so we might as well sort the array first, which makes it easy to skip duplicate elements.
Next, we enumerate the first element of the triplet nums[i], where 0 ≤ i \lt n - 2. For each i, we can find j and k satisfying nums[i] + nums[j] + nums[k] = 0 by maintaining two pointers j = i + 1 and k = n - 1. In the enumeration process, we need to skip duplicate elements to avoid duplicate triplets.
The specific judgment logic is as follows:
If i \gt 0 and nums[i] = nums[i - 1], it means that the element currently enumerated is the same as the previous element, we can skip it directly, because it will not produce new results.
If nums[i] \gt 0, it means that the element currently enumerated is greater than 0, so the sum of three numbers must not be equal to 0, and the enumeration ends.
Otherwise, we let the left pointer j = i + 1, and the right pointer k = n - 1. When j \lt k, the loop is executed, and the sum of three numbers x = nums[i] + nums[j] + nums[k] is calculated and compared with 0:
- If x \lt 0, it means that nums[j] is too small, we need to move j to the right. - If x \gt 0, it means that nums[k] is too large, we need to move k to the left. - Otherwise, it means that we have found a valid triplet, add it to the answer, move j to the right, move k to the left, and skip all duplicate elements to continue looking for the next valid triplet.
After the enumeration is over, we can get the answer to the triplet.
The time complexity is O(n^2), and the space complexity is O(log n). The n is the length of the array.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j = i + 1, k = n - 1;
while (j < k) {
int x = nums[i] + nums[j] + nums[k];
if (x < 0) {
++j;
} else if (x > 0) {
--k;
} else {
ans.add(List.of(nums[i], nums[j++], nums[k--]));
while (j < k && nums[j] == nums[j - 1]) {
++j;
}
while (j < k && nums[k] == nums[k + 1]) {
--k;
}
}
}
}
return ans;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.