代码随想录算法训练营第第七天 | 454.四数相加II 、383. 赎金信 、15. 三数之和 、18. 四数之和

454.四数相加II

建议：本题是 使用map 巧妙解决的问题，好好体会一下 哈希法 如何提高程序执行效率，降低时间复杂度，当然使用哈希法 会提高空间复杂度，但一般来说我们都是舍空间 换时间， 工业开发也是这样。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0454.四数相加II.html

主要利用哈希表，关键是key和value存什么。
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function(nums1, nums2, nums3, nums4) {
    let sum12Map = new Map();
    for(let i=0;i<nums1.length;i++){
        for(let j=0;j<nums2.length;j++){
            let sum = nums1[i] + nums2[j];
            sum12Map.set(sum, (sum12Map.get(sum) || 0) + 1);
        }
    }
    let count = 0;
     for(let i=0;i<nums3.length;i++){
        for(let j=0;j<nums4.length;j++){
            let sum = 0-(nums3[i] + nums4[j]);
            if(sum12Map.has(sum)){
                count += sum12Map.get(sum);
            }
        }
    }
    return count;
};

383. 赎金信

建议：本题 和 242.有效的字母异位词 是一个思路 ，算是拓展题
题目链接/文章讲解：https://programmercarl.com/0383.赎金信.html

这题我用哈希保存数据，当然也可以用数组
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    let rLen = ransomNote.length;
    let mLen = magazine.length;
    if(mLen<rLen){
        return false;
    }
    

    const map = new Map();
    for(let r of ransomNote){
        map.set(r, (map.get(r)|| 0)+1);
    }

    for(let m of magazine){
        if(map.has(m)){
            map.set(m, map.get(m)-1);
        }
    }

    for(let val of map.values()){
        if(val>0){
            return false;
        }
    }

    return true;
};

15. 三数之和

建议：本题虽然和 两数之和 很像，也能用哈希法，但用哈希法会很麻烦，双指针法才是正解，可以先看视频理解一下 双指针法的思路，文章中讲解的，没问题 哈希法很麻烦。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0015.三数之和.html

这题不看题解根本没啥思路，后续这题要二刷，顺便写下用哈希表存储的方法
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a,b)=>a-b);
    const res = [];
    let len = nums.length;
    for(let i=0;i<len;i++){
        let left = i+1;
        let right = len-1;
        if(nums[i]>0) return res;
        if(i>0&&nums[i]===nums[i-1]) continue
        while(left<right){
            let sum = nums[i]+nums[right]+nums[left];
            if(sum<0){
                left++;
            }else if(sum>0){
                right--;
            }else {
                res.push([nums[i],nums[left],nums[right]]);
                while(left<right&&nums[left]===nums[left+1]){
                    left++;
                }
                while(left<right&&nums[right] === nums[right-1]){
                    right--;
                }
                left++;
                right--;
            }   
        }
    }
    return res;
};

18. 四数之和

建议： 要比较一下，本题和 454.四数相加II 的区别，为什么 454.四数相加II 会简单很多，这个想明白了，对本题理解就深刻了。 本题 思路整体和 三数之和一样的，都是双指针，但写的时候 有很多小细节，需要注意，建议先看视频。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0018.四数之和.html

这题和三数之和类似，关键在于每个数的去重
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    let len = nums.length;
    if(len<4) return [];
    nums.sort((a,b)=>a-b);
    const res = [];
    for(let i=0;i<len-3;i++){
        if(i>0&&nums[i]===nums[i-1]) continue;
        for(let j=i+1;j<len-2;j++){
            let l = j+1;
            let r = len-1;
            if(j>i+1 && nums[j] === nums[j-1]) continue;
            while(l<r){
                let sum = nums[i]+nums[j]+nums[l]+nums[r];
                if(sum>target){
                    r--;
                }else if(sum<target){
                    l++
                }else{
                    res.push([nums[i],nums[j],nums[l],nums[r]]);
                    while(l<r&&nums[l]===nums[l+1]){
                        l++;
                    }
                    while(l<r&&nums[r]===nums[r-1]){
                        r--;
                    }
                    l++;
                    r--;
                }
            }
        }
    }
    return res;
};