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

今日学习的文章链接和视频链接

• https://programmercarl.com/链表理论基础.html

● 454.四数相加II

var fourSumCount = function(nums1, nums2, nums3, nums4) {
    let count = 0
    let map = new Map();
    for(let number1 of nums1){
        for(let number2 of nums2){
            let sum = number1 + number2;
            if(!map.get(sum)){
                map.set(sum,1)
            }else{
                map.set(sum ,map.get(sum)+1)
            }
        }
    }
    for(let number1 of nums3){
        for(let number2 of nums4){
            let sum = number1+number2;
            if(map.get(0-sum)){
                count+= map.get(0-sum)
            }
        }
    }
    return count

};

● 383. 赎金信

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

};

● 15. 三数之和

var threeSum = function(nums) {
    let res = [] ;
    let len = nums.length;
    nums.sort((a,b)=>a-b)
    for(let i = 0 ; i < nums.length ; i++){
        let l = i + 1;
        let r = len-1 ; 
        if(nums[i]>0) return res;
        if(i>0&& nums[i] == nums[i-1]){
            continue;
        }
        while(l<r){
            let sum = nums[i] + nums[l] + nums[r];
            if(sum < 0 ){
            l++
        }else if(sum > 0 ){
            r--
        }else{
            res.push([nums[i],nums[l],nums[r]])
            while(nums[r] == nums[r-1]){
                r--
            }
            while(nums[l] === nums[l+1]){
                l++
            }
            r--;
            l++;
        }
        }
        
    }
    return res

};

● 18. 四数之和

var fourSum = function (nums, target) {
    if (nums.length < 4) return []
    nums.sort((a, b) => a - b)
    let res = []
    for (let k = 0; k < nums.length - 3; k++) {
        if (k > 0 && nums[k] == nums[k - 1]) continue;
        for (let i = k + 1; i < nums.length - 2; i++) {
            if (i > k + 1 && nums[i] == nums[i - 1]) continue;
            let l = i + 1;
            let r = nums.length - 1;

            while (l < r) {
                let sum = nums[k] + nums[i] + nums[l] + nums[r];
                if (sum < target) {
                    l++;
                    continue
                } else if (sum > target) {
                    r--;
                    continue
                } else {
                    res.push([nums[k], nums[i], 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

};

今日收获，记录一下自己的学习时长

3h