代码随想录训练营Day7|454. 四数相加 II, 383.赎金信, 15.三数之和, 18.四数之和

454. 四数相加 II

解题思路

• 定义哈希表 map
• 记录 nums1 和 nums2 各个元素两两相加和及出现的次数，key=和，value=和出现的次数。
• 记录 nums2 和 nums3 各个元素两两相加和，如果map存在0 - (k + l)的key，说明满足 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0，由于不需要考虑重复元素，统计其出现的次数即可。

var fourSumCount = function(nums1, nums2, nums3, nums4) {
    let map = new Map();
    for (let i of nums1) {
        for (let j of nums2) {
            map.set(i+j, (map.get(i+j) || 0) + 1)
        }
    }
    let count = 0;
    for (let k of nums3) {
        for (let l of nums4) {
            count += map.get(0 - (k+l)) || 0
        }
    }
    return count;
};

383. 赎金信

解题思路

实现一

• 哈希解法 - Map
• 由于magazine 中的每个字母只能在 ransomNote 中使用一次，所以至少要统计magazine中各个字母出现的次数。
• 遍历ransomNote，如果ransomNote中的字母不存在map中或者次数已用完，说明ransomNote所需要的字母 magazine 不能满足，返回 false；。

var canConstruct = function(ransomNote, magazine) {
    let map = new Map()
    for (let i of magazine){
        map.set(i,(map.get(i) || 0)+1)
    }
    for(let i of ransomNote){
        if (!map.get(i)) {
            return false;
        }
        map.set(i, map.get(i) - 1)
    }
    return true
};

实现二

• 哈希解法 - Array
• 由于题目说明 ransomNote 和 magazine 由小写英文字母组成，所以最大长度是可以确定为26的。
• 在长度可以确定的情况下，由于使用 Map 的空间消耗要比 Array 大一些的，因此可以使用数组求解。

var canConstruct = function(ransomNote, magazine) {
    const strArr = new Array(26).fill(0);
    const base = "a".charCodeAt();
    for (let i of magazine) {
        strArr[i.charCodeAt() - base]++;
    }
    for (let i of ransomNote) {
        const index = i.charCodeAt() - base;
        if (!strArr[index]) {
            return false
        }
        strArr[index]--
    }
    return true
};

15. 三数之和

解题思路

• 特殊判断，if (nums.length < 3) return false
• 对 nums 排序，从索引 i = 0 开始，使用双指针依次求和，收缩后续元素
• left = i + 1 ，right = nums.length - 1
• if (arr[left] + arr[right] + arr[i] < 0) left++
• if (arr[left] + arr[right] + arr[i] > 0) right--
• else 保留一组结果值

难点

目标找出a + b + c = 0，且不可以包含重复的三元组，注意 [0,0,0,0]
a = nums[i], b = nums[left], c = nums[right]

• 去重
  去重a：if (i > 0 && arr[i]==arr[i-1]) continue
  去重b：while(left < right && arr[left] === arr[left+1]) { left++ }
  去重c：while(left < right && arr[right] === arr[right-1]) { right-- }

var threeSum = function(nums) {
    if (nums.length < 3) {
        return []
    }
    let arr = nums.sort((a, b) => a - b)
    let left = 0;
    let right = arr.length - 1;
    let res = []
    for(let i = 0;i<arr.length;i++){
        // 如果排序后的第1个元素大于0，那么不可能凑成满足条件的三元组
        if(arr[i]>0) {
            return res
        }
        // 错误去重a方法，将会漏掉-1,-1,2 这种情况
        /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
        */
        if(i>0 && arr[i]==arr[i-1]) {
            continue
        }
        left = i+1
        right = arr.length - 1
        while(left < right) {
            if (arr[left]+arr[right] +arr[i] < 0){
                left++
            } else if(arr[left]+arr[right] +arr[i] > 0){
                right--
            } else {
                // 优先保存一组满足条件的元组
                res.push([arr[i],arr[left],arr[right]])
                // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                while(left < right && arr[left] === arr[left+1]) {
                    left++
                }
                while(left < right && arr[right] === arr[right-1]) {
                    right--
                }
                left++
                right--
            }
        }
    }
    return res;
};

18. 四数之和

解题思路

• 本题同15. 三数之和类似，看上去多了一层循环。
• 注意目标值 target 不再是0，有可能是负数，比如排序后的数组arr = [-4, -3, -2, -1]，target = -10，那么arr[0] > target，但是仍然存在满足条件的元组。
• 第一层剪枝，满足 if(arr[i]>target && (arr[i] >= 0 || target >= 0)) { break }，则说明不会出现满足条件的四元组。
• 第一层去重，同15. 三数之和处理相同。
• 第二层剪枝，if(arr[i] + arr[j] >target && arr[i] + arr[j] > 0) { break }
• 第二层去重，if (arr[j] === arr[j-1] && j > i+1) { continue }
• 剩余处理同15. 三数之和

var fourSum = function(nums, target) {
    let arr = nums.sort((a, b) => a - b);
    let res = [];
    let left = 0;
    let right = arr.length - 1;
    for (let i = 0; i < arr.length; i++) {
        if(arr[i]>target && (arr[i] >= 0 || target >= 0)) { // 一层剪枝
            break
        }
        if (arr[i] === arr[i-1] && i > 0) { // 一层去重
            continue
        }
        for (let j = i+1; j<arr.length; j++) {
            if(arr[i] + arr[j] >target && arr[i] + arr[j] > 0) { // 二层剪枝
                break
            }
            if (arr[j] === arr[j-1] && j > i+1) { 二层去重
                continue
            }
            left = j+1
            right = arr.length - 1
            while(left < right) {
                if (arr[left]+arr[right] +arr[i] + arr[j] < target){
                    left++
                } else if(arr[left]+arr[right] +arr[i] + arr[j] > target){
                    right--
                } else {
                    res.push([arr[i],arr[j],arr[left],arr[right]])
                    while(left < right && arr[left] === arr[left+1]) {
                        left++
                    }
                    while(left < right && arr[right] === arr[right-1]) {
                        right--
                    }
                    left++
                    right--
                }
            }
        }
    }
    return res;
};