代码随想录算法训练营第七天 | 四数相加、赎金信,三数之和,两数之和

第454题.四数相加II

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
            unordered_map<int,int> ma;
            int target = 0;
            int num = 0;
            for (auto i : nums1) {
                for (auto j : nums2) {
                    ma[i+j]++;
                }
            }
            for (auto i : nums3) {
                for (auto j : nums4) {
                    target = 0-(i+j);
                    if(ma.find(target) != ma.end()) num += ma[target];
                }
            }
            return num;
    }
};

383. 赎金信

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
            int num[26] = {0};
            for (int i = 0; i < magazine.size(); ++i) {
                num[magazine[i] - 'a']++;
            }
            for (int j = 0; j < ransomNote.size(); ++j) {
                if (num[ransomNote[j] - 'a'] != 0) num[ransomNote[j] - 'a']--;
                else 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) break; // 大于零直接退出 
                if(i > 0 && nums[i] == nums[i-1]) continue;
                int left = i + 1;
                int right = nums.size() - 1;
                while(left < right) {
                    int sum = nums[i] + nums[left] + nums[right];
                    if (sum > 0) right--;
                    else if (sum < 0) left++;
                    else {
                        result.push_back(vector<int>({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 result;
    }
};

第18题. 四数之和

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
            sort(nums.begin(),nums.end());
            vector<vector<int>> result;
            for (int i = 0; i < nums.size(); ++i) {
                if(nums[i] > target && nums[i] > 0) break; // 剪枝
                if (i > 0 && nums[i] == nums[i-1]) continue;  // 去重
                for (int j = i+1; j < nums.size();++j) {
                    if (nums[i] + nums[j] > target && nums[i] + nums[j] > 0) break;
                    if (j > i +1  && nums[j] == nums[j-1]) continue;
                    int left = j + 1;
                    int right = nums.size() - 1;
                    while(left < right) {
                        long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                        if (sum > target) right--;
                        else if (sum < target) left++;
                        else {
                            result.push_back(vector<int>({nums[i],nums[j],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 result;
    }
};