三数之和
1、题目描述
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
1 | 输入:nums = [-1,0,1,2,-1,-4] |
示例 2:
1 | 输入:nums = [0,1,1] |
示例 3:
1 | 输入:nums = [0,0,0] |
提示:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
2、题解
2.1 排序+双指针
先将
nums
排序,时间复杂度为 *O(NlogN)*。固定 3 个指针中最左(最小)元素的指针
k
,双指针i
,j
分设在数组索引 *(k,len(nums))*两端。双指针 i , j 交替向中间移动,记录对于每个固定指针
k
的所有满足nums[k] + nums[i] + nums[j] == 0
的i
,j
组合:- 当
nums[k] > 0
时直接break
跳出:因为nums[j] >= nums[i] >= nums[k] > 0
,即 3 个元素都大于 0 ,在此固定指针k
之后不可能再找到结果了。 - 当
k > 0
且nums[k] == nums[k - 1]
时即跳过此元素nums[k]
:因为已经将nums[k - 1]
的所有组合加入到结果中,本次双指针搜索只会得到重复组合。 i
,j
分设在数组索引 (k,len(nums)) 两端,当i < j
时循环计算s = nums[k] + nums[i] + nums[j]
,并按照以下规则执行双指针移动:- 当
s < 0
时,i += 1
并跳过所有重复的nums[i]
; - 当
s > 0
时,j -= 1
并跳过所有重复的nums[j]
; - 当
s == 0
时,记录组合[k, i, j]
至res
,执行i += 1
和j -= 1
并跳过所有重复的nums[i]
和nums[j]
,防止记录到重复组合。
- 当
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
38from typing import List
class Solution(object):
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res, k = [], 0
for k in range(len(nums) - 2):
# 1. because of j > i > k.
if nums[k] > 0:
break
# 2. skip the same `nums[k]`.
if k > 0 and nums[k] == nums[k - 1]:
continue
i, j = k + 1, len(nums) - 1
while i < j:
s = nums[k] + nums[i] + nums[j]
if s < 0:
i += 1
while i < j and nums[i] == nums[i - 1]:
i += 1
elif s > 0:
j -= 1
while i < j and nums[j] == nums[j + 1]:
j -= 1
else:
res.append([nums[k], nums[i], nums[j]])
i += 1
j -= 1
while i < j and nums[i] == nums[i + 1]:
i += 1
while i < j and nums[j] == nums[j - 1]:
j -= 1
return res
solution = Solution()
print(solution.threeSum([-1, 0, 1, 2, -1, -4]))1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int k = 0; k < nums.length - 2; k++) {
if (nums[k] > 0) break;
if (k > 0 && nums[k] == nums[k - 1]) continue;
int i = k + 1, j = nums.length - 1;
while (i < j) {
int sum = nums[k] + nums[i] + nums[j];
if (sum < 0) {
while (i < j && nums[i] == nums[++i]) ;
} else if (sum > 0) {
while (i < j && nums[j] == nums[--j]) ;
} else {
res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
while (i < j && nums[i] == nums[++i]) ;
while (i < j && nums[j] == nums[--j]) ;
}
}
}
return res;
}
}- 当
复杂度分析:
- 时间复杂度 O(N2):其中固定指针
k
循环复杂度 O(N),双指针i
,j
复杂度 O(N)。 - 空间复杂度 O(1):指针使用常数大小的额外空间。
- 时间复杂度 O(N2):其中固定指针