江月迟迟的个人知识库

外观

两数之和模块 ​

作者:江月迟迟
发表于:2024-12-16
字数统计:1452 字
预计阅读5分钟

知识点 ​

双指针、哈希表

题单 ​

1. 两数之和

15. 三数之和

18. 四数之和

454. 四数相加 II

解析 ​

1. 两数之和 ​

两数之和意图找到a + b === target，a,b出自数组中。那么最简单的思路就是暴力枚举，对每个元素，向后遍历整个数组，寻找是否有与这个元素达成筛选条件的另一个元素，如果有，记录答案；如果没有，遍历下一个元素。

js
var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++) {
        for(let j = i + 1; j < nums.length; j++) {
            const a = nums[i], b = nums[j]
            if(a + b === target) return [i, j]
        }
    }
    return [-1, -1]
}

显然是平方复杂度。

上面的第二层for循环实际上是在做一个查找操作，如果我么能把查找操作简化，时间复杂度会进一步降低。应该用哈希查找。

哈希查找的思路：将所有数据存入哈希表，然后查找即可。这使用了两个for循环。显然可以一边存入哈希表，一边查找答案。

js
var twoSum = function(nums, target) {
    const map = new Map()
    for(let i = 0; i < nums.length; i++) {
        if(map.has(target - nums[i])) {
            return [map.get(target - nums[i]), i]
        } else {
            map.set(nums[i], i)
        }
    }
    return [1, 1]
};

15. 三数之和 ​

筛选条件是：a + b + c === target暴力思路同上，相比于两数之和，多了一个数，没法直接用哈希查找优化成更简单的形式，只能在外层包一层遍历的a。也只需要外层包裹一层起点就行了。

js
var threeSum = function(nums) {
    const result = []
    for(let i = 0; i < nums.length; i++) {
        // a + b + c === 0 ---> b + c === -a
        const a = nums[i]
        const ans = twoSum(nums.slice(i+1), -a)
        if(ans.length) {
            ans.forEach(item => result.push([a, ...item]))
        }
    }
    return result


    function twoSum(nums, target) {
        const map = new Map()
        const result = []
        for(let i = 0; i < nums.length; i++) {
            if(map.has(target - nums[i])) {
                result.push([map.get(target - nums[i]), nums[i]])
            } else {
                map.set(nums[i], nums[i])
            }
        }
        return result
    };
}

时间复杂度是平方。思路完成了，但是跑上述代码是行不通的，因为本题还有一个去重逻辑。请你返回所有和为 0 且不重复的三元组

可以使用（排序后）哈希表去重或者排序后双指针去重。

js
// 哈希表去重
var threeSum = function(nums) {
    const result = []
    nums.sort((a,b) => a-b)
    const used = new Set()
    for(let i = 0; i < nums.length; i++) {
        // a + b + c === 0 ---> b + c === -a
        const a = nums[i]
        const two = twoSum(nums.slice(i+1), -a)
        if(two.length) {
            two.forEach(item => {
                const ans = [a, ...item]
                if(!used.has(ans.toString())) {
                    used.add(ans.toString())
                    result.push(ans)
                }
            })
        }
    }
    return result


    function twoSum(nums, target) {
        const map = new Map()
        const result = []
        for(let i = 0; i < nums.length; i++) {
            if(map.has(target - nums[i])) {
                result.push([map.get(target - nums[i]), nums[i]])
            } else {
                map.set(nums[i], nums[i])
            }
        }
        return result
    };
}

然而还是不对，最后会超出时间限制，平方还是蛮高的，所以需要剪枝。

剪枝内容：下一个a和上一个a相同，跳过。

js
var threeSum = function(nums) {
    const result = []
    nums.sort((a,b) => a-b)
    const used = new Set()
    for(let i = 0; i < nums.length; i++) {
        // a + b + c === 0 ---> b + c === -a
        const a = nums[i]
        // 剪枝1.下一个a和上一个a相同，跳过。
        if(i >= 1 && a === nums[i-1]) continue
        const two = twoSum(nums.slice(i+1), -a)
        if(two.length) {
            two.forEach(item => {
                const ans = [a, ...item]
                if(!used.has(ans.toString())) {
                    used.add(ans.toString())
                    result.push(ans)
                }
            })
        }
    }
    return result


    function twoSum(nums, target) {
        const map = new Map()
        const result = []
        for(let i = 0; i < nums.length; i++) {
            if(map.has(target - nums[i])) {
                result.push([map.get(target - nums[i]), nums[i]])
            } else {
                map.set(nums[i], nums[i])
            }
        }
        return result
    };
}

双指针写法

双指针需要保障答案在进入的时候就没有重复的，所以不复用之前代码。

js
var threeSum = function(nums) {
    const result = []
    nums.sort((a,b) => a-b)
    for(let i = 0; i < nums.length; i++) {
        let left = i + 1
        let right = nums.length - 1
        if(i > 0 && nums[i] === nums[i-1]) continue
        while(left < right) {
            const sum = nums[i] + nums[left] + nums[right]
            if(sum > 0) {
                right--
            } else if (sum < 0) {
                left++
            } else {
                const n1 = nums[left]
                const n2 = nums[right]
                result.push([nums[i], n1, n2])
                while(left < right && n1 === nums[left]) {
                    left++
                }
                while(left < right && n2 === nums[right]) {
                    right--
                }
            }
        }
    }
    return result
};

18. 四数之和 ​

四数之和就是a + b + c + d === target，又在外面包了一层。

本题仍有去重逻辑，直接写就行。

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    const set = new Set()
    const result = []
    nums.sort((a,b) => a-b)
    for(let k = 0; k < nums.length; k++) {

        // 剪枝：nums[k] > target && nums[k] >= 0
        if(nums[k] > target && nums[k] >= 0) {
            break
        }

        // 剪枝：去重的逻辑
        if(k > 0 && nums[k] === nums[k-1]) {
            continue
        }

        for(let i = k + 1; i < nums.length; i++) {

            // 剪枝：nums[k] + nums[i] > target 切 nums[left] > 0，此时调整left,right无用
            if(nums[k] + nums[i] > target && nums[i + 1] >= 0) {
                break
            }

            // 剪枝：去重的逻辑
            if(i > k + 1 && nums[i] === nums[i-1]) {
                continue
            }

            let left = i + 1
            let right = nums.length - 1
            while(left < right) {
                const sum = nums[k] + nums[i] + nums[left] + nums[right]
                if(sum > target) {
                    right--
                } else if (sum < target) {
                    left++
                } else {
                    // set开始
                    // const arr = [nums[k], nums[i], nums[left], nums[right]]
                    // const str = arr.join(',')
                    // if(!set.has(str)) {
                    //     set.add(str)
                    //     result.push(arr)
                    // }
                    // set结束

                    // 直接去重开始
                    result.push([nums[k], nums[i], nums[left], nums[right]])
                    while(left < right && nums[right] === nums[right-1]) right--
                    while(left < right && nums[left] === nums[left + 1]) left++
                    // 直接去重结束

                    left++
                    right--
                }
            }
        }
    }
    return result
};

454. 四数相加 II ​

其实啥也不是，就是前两个做target，后两个找答案。

js
var fourSumCount = function(nums1, nums2, nums3, nums4) {
    // a + b + c + d === target ---> c + d === target - a - b
    // 本题target为0
    // 不需要去重，只用返回方案数
    const targetMap = new Map()
    let ans = 0
    for(let a of nums1) {
        for(let b of nums2) {
            targetMap.set(a + b, (targetMap.get(a + b) || 0) + 1)
        }
    }
    // 从数出的targetMap中找答案
    for(let c of nums3) {
        for(let d of nums4) {
            ans += targetMap.get(0 - c - d) || 0
        }
    }
    return ans
};