力扣-15.三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
1
2
3
4
5
6
7
8
| 输入：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] 。
注意，输出的顺序和三元组的顺序并不重要。
|
示例 2：
1
2
3
| 输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
|
示例 3：
1
2
3
| 输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
|
解题思路
最开始想到的就是暴力解法，先将数组排序，接着三层循环控制i != j、i != k 且 j != k，当nums[i]+nums[j]+nums[k]==0时，将三元组存入结果数组中。但显然时间复杂度过高需要优化。看了题解学习了双指针将时间复杂度优化到o(n^2)。排序时间复杂度是o(nlogn)，外层循环枚举第一个数A时间复杂度为o(n)，就变成寻找两个数B,C的和为-A的问题(即两数之和),双指针o(n)，总时间复杂度o(n^2)
代码实现
1.暴力解法[TC:O(n^3) SC:O(n)]，示例过，but力扣显示超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| var threeSum = function(nums) {
//将数组进行排序
nums = nums.sort((a,b) => a-b)
let res = []
for(let i = 0;i < nums.length;i ++){
//当i不等于0且当前数字等于上一个数字时，该数字在上轮循环中已得出结果，为避免重复则跳过
if(i != 0 && nums[i] == nums[i-1]) continue
for(let j = i + 1;j < nums.length;j ++){
//同上
if(j != i + 1 && nums[j] == nums[j-1]) continue
for(let k = j + 1;k < nums.length;k ++){
//同上
if(k != j + 1 && nums[k] == nums[k-1]) continue
if(nums[i] + nums[j] + nums[k] == 0)
res.push(nums[i],nums[j],nums[k])
}
}
return res
}
|
2.双指针优化[TC:O(n^2) SC:O(1)]
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
| var threeSum = function(nums) {
//将数组进行排序
nums.sort((a,b) => a-b)
let n = nums.length
let res = []
// i最大取到n-3,剩两位留给j,k
for(let i = 0;i < n - 2;i ++){
//第一个取值重复跳过
if(i != 0 && nums[i] == nums[i-1]) continue
//加上最小的两个数都大于0，i就不用再加了
if(nums[i] + nums[i+1] + nums[i+2] > 0) break
//加上最大的两个数还要小,i还需要增大
if(nums[i] + nums[n-2] + nums[n-1] < 0) continue
let j = i + 1
let k = n - 1
while(j < k){
if(nums[i] + nums[j] + nums[k] < 0)
j ++
else if(nums[i] + nums[j] + nums[k] > 0)
k --
else{
res.push([nums[i],nums[j],nums[k]])
j ++
//第二个取值重复跳过
while( j < k && nums[j] == nums[j-1]) j ++
k--
//第三个取值重复跳过
while( k > j && nums[k] == nums[k-1]) k --
}
}
return res
}
|
