题解 | #三数之和#

/**
 * 解法一：双指针
 * 思路：待补充
 * 时间复杂度：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
}

一站式解决前端面试高频算法题

https://github.com/hovinghuang/fe-agorithm-interview