Problem
Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0.
Example
Input: [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]Solution
Sort the array. For each element, use two pointers on the rest to find pairs that sum to its negation.
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue
l, r = i + 1, len(nums) - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total < 0: l += 1
elif total > 0: r -= 1
else:
result.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]: l += 1
while l < r and nums[r] == nums[r-1]: r -= 1
l += 1; r -= 1
return resultfunction 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 l = i + 1, r = nums.length - 1;
while (l < r) {
const total = nums[i] + nums[l] + nums[r];
if (total < 0) l++;
else if (total > 0) r--;
else {
result.push([nums[i], nums[l], nums[r]]);
while (l < r && nums[l] === nums[l+1]) l++;
while (l < r && nums[r] === nums[r-1]) r--;
l++; r--;
}
}
}
return result;
}vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for (int i = 0; i < (int)nums.size() - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
int l = i + 1, r = nums.size() - 1;
while (l < r) {
int total = nums[i] + nums[l] + nums[r];
if (total < 0) l++;
else if (total > 0) r--;
else {
result.push_back({nums[i], nums[l], nums[r]});
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++; r--;
}
}
}
return result;
}public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
int l = i + 1, r = nums.length - 1;
while (l < r) {
int total = nums[i] + nums[l] + nums[r];
if (total < 0) l++;
else if (total > 0) r--;
else {
result.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l+1]) l++;
while (l < r && nums[r] == nums[r-1]) r--;
l++; r--;
}
}
}
return result;
}Complexity
- Time: O(n²)
- Space: O(1) extra
Explanation
Sorting enables the two-pointer technique. The skip-duplicate logic prevents duplicate triplets in the output.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?