11. 哈希表

11.1 242. 有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26]={0};
        //记录s每个字母出现次数
        for(int i=0;i<s.size();i++){
            record[s[i]-'a']++;
        }
        //记录t中每个字母出现次数，想减，最后都为0才是true；
        for(int i=0;i<t.size();i++){
            record[t[i]-'a']--;
        }
        for(int i=0;i<26;i++){
            if(record[i]!=0){
                return false;
            }
        }
        return true;
    }
};

11.2 1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(int i=0;i<nums.size();i++){
            auto it=map.find(target-nums[i]);
            if(it!=map.end()){
                return {it->second,i};
            }
            map.insert(pair<int,int>(nums[i],i));
        }
        return {};
    }
};

11.3 454. 四数相加 II

//两两结合
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){
                auto it=map.find(0-(c+d));
                if(it!=map.end()){
                    count+=map[0-(c+d)];
                }
            }
        }
        return count;
    }
};

11.4 383. 赎金信

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