15. 3Sum
給定一個整數數組 nums，返回所有的三元組 [nums[i], nums[j], nums[k]]，使得 i != j、i != k、j != k 且 nums[i] + nums[j] + nums[k] == 0。
注意，解集不得包含重複的三元組。
範例 1：
輸入：nums = [-1,0,1,2,-1,-4] 輸出：[[-1,-1,2],[-1,0,1]] 解釋： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0。 不同的三元組是 [-1,0,1] 和 [-1,-1,2]。 注意，輸出和三元組的順序無關。
Python
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# Sort the array to facilitate the two-pointer technique
nums.sort()
result = []
for i in range(len(nums)):
# Avoid duplicates for the first element of the triplet
if i > 0 and nums[i] == nums[i - 1]:
continue
# Use two pointers to find the remaining two elements
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
# Avoid duplicates for the second element of the triplet
while left < right and nums[left] == nums[left + 1]:
left += 1
# Avoid duplicates for the third element of the triplet
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
20.6MB, 707ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end()); // Sort the array to use the two-pointer
technique
for (int i = 0; i < nums.size(); ++i) {
// Avoid duplicates for the first element of the triplet
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
// Avoid duplicates for the second element of the triplet
while (left < right && nums[left] == nums[left + 1]) {
++left;
}
// Avoid duplicates for the third element of the triplet
while (left < right && nums[right] == nums[right - 1]) {
--right;
}
++left;
--right;
} else if (sum < 0) {
++left;
} else {
--right;
}
}
}
return result;
}
};
27.08MB, 65ms
Javascript
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const result = [];
nums.sort((a, b) => a - b); // Sort the array to use the two-pointer technique
for (let i = 0; i < nums.length; i++) {
// Avoid duplicates for the first element of the triplet
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]]);
// Avoid duplicates for the second element of the triplet
while (left < right && nums[left] === nums[left + 1]) {
left++;
}
// Avoid duplicates for the third element of the triplet
while (left < right && nums[right] === nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
};
63.82MB, 156ms
