题目描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000-105 <= nums[i] <= 105
注意：本题与主站 15 题相同：https://leetcode.cn/problems/3sum/
解法
方法一：排序 + 双指针
我们注意到，题目不要求我们按照顺序返回三元组，因此我们不妨先对数组进行排序，这样就可以方便地跳过重复的元素。
接下来，我们枚举三元组的第一个元素 $nums[i]$，其中 $0 \leq i \lt n - 2$。对于每个 $i$，我们可以通过维护两个指针 $j = i + 1$ 和 $k = n - 1$，从而找到满足 $nums[i] + nums[j] + nums[k] = 0$ 的 $j$ 和 $k$。在枚举的过程中，我们需要跳过重复的元素，以避免出现重复的三元组。
具体判断逻辑如下：
如果 $i \gt 0$ 并且 $nums[i] = nums[i - 1]$，则说明当前枚举的元素与上一个元素相同，我们可以直接跳过，因为不会产生新的结果。
如果 $nums[i] \gt 0$，则说明当前枚举的元素大于 $0$，则三数之和必然无法等于 $0$，结束枚举。
否则，我们令左指针 $j = i + 1$，右指针 $k = n - 1$，当 $j \lt k$ 时，执行循环，计算三数之和 $x = nums[i] + nums[j] + nums[k]$，并与 $0$ 比较：
- 如果 $x \lt 0$，则说明 $nums[j]$ 太小，我们需要将 $j$ 右移一位。
- 如果 $x \gt 0$，则说明 $nums[k]$ 太大，我们需要将 $k$ 左移一位。
- 否则，说明我们找到了一个合法的三元组，将其加入答案，并将 $j$ 右移一位，将 $k$ 左移一位，同时跳过所有重复的元素，继续寻找下一个合法的三元组。
枚举结束后，我们即可得到三元组的答案。
时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ans = []
for i in range(n - 2):
if nums[i] > 0:
break
if i and nums[i] == nums[i - 1]:
continue
j, k = i + 1, n - 1
while j < k:
x = nums[i] + nums[j] + nums[k]
if x < 0:
j += 1
elif x > 0:
k -= 1
else:
ans.append([nums[i], nums[j], nums[k]])
j, k = j + 1, k - 1
while j < k and nums[j] == nums[j - 1]:
j += 1
while j < k and nums[k] == nums[k + 1]:
k -= 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {
if (i && 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.push_back({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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | func threeSum(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
for i := 0; i < n-2 && nums[i] <= 0; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
j, k := i+1, n-1
for j < k {
x := nums[i] + nums[j] + nums[k]
if x < 0 {
j++
} else if x > 0 {
k--
} else {
ans = append(ans, []int{nums[i], nums[j], nums[k]})
j, k = j+1, k-1
for j < k && nums[j] == nums[j-1] {
j++
}
for j < k && nums[k] == nums[k+1] {
k--
}
}
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const ans: number[][] = [];
const n = nums.length;
for (let i = 0; i < n - 2 && nums[i] <= 0; i++) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
let j = i + 1;
let k = n - 1;
while (j < k) {
const x = nums[i] + nums[j] + nums[k];
if (x < 0) {
++j;
} else if (x > 0) {
--k;
} else {
ans.push([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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | use std::cmp::Ordering;
impl Solution {
pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort();
let n = nums.len();
let mut res = vec![];
let mut i = 0;
while i < n - 2 && nums[i] <= 0 {
let mut l = i + 1;
let mut r = n - 1;
while l < r {
match (nums[i] + nums[l] + nums[r]).cmp(&0) {
Ordering::Less => {
l += 1;
}
Ordering::Greater => {
r -= 1;
}
Ordering::Equal => {
res.push(vec![nums[i], nums[l], nums[r]]);
l += 1;
r -= 1;
while l < n && nums[l] == nums[l - 1] {
l += 1;
}
while r > 0 && nums[r] == nums[r + 1] {
r -= 1;
}
}
}
}
i += 1;
while i < n - 2 && nums[i] == nums[i - 1] {
i += 1;
}
}
res
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | /**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const n = nums.length;
nums.sort((a, b) => a - b);
const ans = [];
for (let i = 0; i < n - 2 && nums[i] <= 0; ++i) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
let j = i + 1;
let k = n - 1;
while (j < k) {
const x = nums[i] + nums[j] + nums[k];
if (x < 0) {
++j;
} else if (x > 0) {
--k;
} else {
ans.push([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;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
Array.Sort(nums);
int n = nums.Length;
IList<IList<int>> ans = new List<IList<int>>();
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(new List<int> { 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | # @param {Integer[]} nums
# @return {Integer[][]}
def three_sum(nums)
res = []
nums.sort!
for i in 0..(nums.length - 3)
next if i > 0 && nums[i - 1] == nums[i]
j = i + 1
k = nums.length - 1
while j < k do
sum = nums[i] + nums[j] + nums[k]
if sum < 0
j += 1
elsif sum > 0
k -= 1
else
res += [[nums[i], nums[j], nums[k]]]
j += 1
k -= 1
j += 1 while nums[j] == nums[j - 1]
k -= 1 while nums[k] == nums[k + 1]
end
end
end
res
end
|