/**
* 解法一:双指针
* 思路:待补充
* 时间复杂度:O(n^2)
* 空间复杂度:待补充
*/
export function threeSum(num: number[]): number[][] {
const res: number[][] = []
const len = num.length
if (len < 3) return res
num.sort((a, b) => a - b)
for (let i = 0; i < len - 2; i++) {
// 避免重复元素
if (num[i] == num[i - 1]) continue
const target = -num[i]
let j = i + 1
let k = len - 1
while (j < k) {
// 避免重复元素(为什么要j > i+1,因为下标i跟j可以相同)
if (j > i + 1 && num[j] == num[j - 1]){
j++
continue
}
if (num[k] == num[k + 1]){
k--
continue
}
if (num[j] + num[k] == target) {
res.push([num[i], num[j], num[k]])
j++
k--
} else if (num[j] + num[k] < target) {
j++
} else {
k--
}
}
}
return res
}
一站式解决前端面试高频算法题