3Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. (Note: reordered as [-1,-1,2])
The distinct triplets are [-1,-1,2] and [-1,0,1].
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Sample Input
nums = [-1,0,1,2,-1,-4]
Sample Output
[[-1,-1,2],[-1,0,1]]
Constraints
- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
Test Cases
Case 1
Args: [[-1,0,1,2,-1,-4]]
Expected: [[-1,-1,2],[-1,0,1]]
Case 2
Args: [[]]
Expected: []
Case 3
Args: [[0]]
Expected: []
Topics
Approach: Sort + Two Pointers
Sort the array first. Then iterate through each element as the first number of the triplet. For each fixed first number, use two pointers (left and right) to find pairs that sum to the negative of the first number.
Skip duplicate values at each step to avoid duplicate triplets.
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
Time Complexity: O(n^2) — sorting is O(n log n), the nested loop is O(n^2).
Space Complexity: O(1) extra space (ignoring the output array).
Saved in this browser only. Private to you.