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

454.四数相加II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n

• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

这一题使用哈希表来做，使用unordereed_map，先遍历nums1、nums2，并存入map中，再遍历nums3、nums4，在map中寻找相反数。时间复杂度O（n2）。

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> map;
        
        for(int a : nums1){
            for(int b : nums2){
                map[a+b] ++;
            }
        }
        int count = 0;
        for(int c:nums3){
            for(int d : nums4){
                if(map.find(0-(c+d)) != map.end()){
                    count += map[0-(c+d)];
                }
            }
        }
        return count;
    }
};

383.赎金信

和字母那道题很像，之前刷过了，这里直接贴上了。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        for(int i = 0;i < magazine.length();i++){
            record[magazine[i] - 'a'] ++;
        }
        for(int j = 0;j < ransomNote.length();j++){
            record[ransomNote[j] - 'a'] --;
            if(record[ransomNote[j] - 'a'] < 0){
                return false;
            }
        }
        return true;
    }
};

15. 三数之和

细节太多了，还得刷。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> result;
        for(int i = 0 ; i < nums.size() ; i ++){
            if(nums[i] > 0){
                return result;
            }
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int left = i + 1;
            int right = nums.size() -  1;
            while(right > left){
                if(nums[i] + nums[left] + nums[right] < 0){
                    left++;
                }
                else if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }
                else{
                    result.push_back(vector<int>{nums[i] , nums[left] , nums[right]});
                    while(right > left && nums[right] == nums[right - 1]){
                        right--;
                    }
                    while(right > left && nums[left] == nums[left + 1]){
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};

18. 四数之和

和三数之和一样的解法，回头再来写吧。