题目(medium)
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
思路
这套题用双指针法会比哈希法更加高效。
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
| const threeSum = (nums) => {
const res = [], len = nums.length
nums.sort((a, b) => a - b)
for (let i = 0; i < len; i++) {
let l = i + 1, r = len - 1, iNum = nums[i]
if (iNum > 0) return res
if (iNum == nums[i - 1]) continue
while(l < r) {
let lNum = nums[l], rNum = nums[r], threeSum = iNum + lNum + rNum
if (threeSum < 0) l++
else if (threeSum > 0) r--
else {
res.push([iNum, lNum, rNum])
while(l < r && nums[l] == nums[l + 1]){
l++
}
while(l < r && nums[r] == nums[r - 1]) {
r--
}
l++
r--
}
}
}
return res
};
|
时间复杂度: O(n^2)。
空间复杂度: O(1)。
