3. 哈希

LeetCode.242.有效的字母异位词

// 造个桶判断一下
class Solution {
public:
    bool isAnagram(string s, string t) {
        int cnt[26] = {0};
        for(int i = 0;i < s.size();i++){
            cnt[s[i]-'a']++;
        }
        for(int i = 0;i < t.size();i++){
            cnt[t[i]-'a']--;
        }
        for(int i = 0;i < 26;i++){
            if(cnt[i] != 0) return false;
        }
        return true;
    }
};

LeetCode.349.两个数组的交集

// 造两个桶， 用来去重
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int mp[1005] = {0};
        int anss_mp[1005] = {0};
        vector<int> anss;
        int cnt = 0;
        for(int i = 0;i < nums1.size();i++){
            mp[nums1[i]]++;
        }
        for(int i = 0;i < nums2.size();i++){
            if(mp[nums2[i]] != 0 && anss_mp[nums2[i]] == 0){
                 anss.insert(anss.begin()+cnt,nums2[i]);
                 anss_mp[nums2[i]]++;
                 cnt++;
            }
        }
        return anss;
    }
};

LeetCode.202.快乐数

// 直接放hash里
class Solution {
public:
    bool isHappy(int n) {
        int mp[2005] = {0};
        while(n != 1){
            n = summ(n);
            if(mp[n] != 0) return false;
            mp[n] = 1;
        }
        return true;
    }

    int summ(int n){
        int summ = 0;
        while(n){
            int b = n%10;
            n = n/10;
            summ += b*b;
        }
        return summ;
    }
};

LeetCode.1.两数之和

// 获取下标
// hash存<数字, 下标>
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        for(int i = 0;i < nums.size();i++){
            auto it = mp.find(target - nums[i]);
            if(it != mp.end()){
                return {i, it->second};
            }
            mp[nums[i]] = i;
        }
        return {};
    }
};

LeetCode.454.四数之和

// 统计次数，hash
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> mp;
        for(int i = 0;i < nums1.size();i++){
            for(int j = 0;j < nums2.size();j++){
                mp[nums1[i]+nums2[j]]++;
            }
        }
        int anss = 0;
        for(int k = 0;k < nums3.size();k++){
            for(int l = 0;l < nums4.size();l++){
                if(mp.count(-nums3[k]-nums4[l])){
                    anss += mp[-nums3[k]-nums4[l]];
                }
            }
        }
        return anss;
    }
};

LeetCode.383.赎金信

// 没什么营养
// sort是logn
// 和242几乎一样
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int mp[26] = {0};
        for(int i = 0;i < ransomNote.size();i++){
            mp[ransomNote[i]-'a']++;
        }
        for(int j = 0;j < magazine.size();j++){
            mp[magazine[j]-'a']--;
        }
        for(int i = 0;i < 26;i++){
            if(mp[i] > 0){
                return false;
            }
        }
        return true;
    }
};

LeetCode.15.三数之和

// 找具体的组合，不能用hash
// 由于要去重复，所以要跳过已经验证的节点
// 并且出现满足调节的组合时，不能直接break，因为再往里也可能存在其他组合
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> v;
        for(int i = 0;i < nums.size();i++){
            if(i >= 1 && nums[i] == nums[i-1]){
                continue;
            }
            int l = i+1, r = nums.size()-1;
            int summ = 0;
            while(l < r){
                if(l > i+1 && nums[l] == nums[l-1]){
                    l++;
                    continue;
                }
                summ = nums[i]+nums[l]+nums[r];
                if(summ == 0){
                    v.push_back({nums[i],nums[l],nums[r]});
                    l++;
                }
                if(summ > 0) r--;
                if(summ < 0) l++;
            }
        }
        return v;
    }
};

LeetCode.18.四数之和

// 注意summ可能为long
// 注意找到target后l的移动，首先要判断左右边界，其次无论匹配不匹配都要先走一步，所以用do-while好过while
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> anss;
        sort(nums.begin(),nums.end());
        for(int i = 0;i < n-1;i++){
            if(i >= 1 && nums[i] == nums[i-1]) continue;
            for(int j = i+1;j < n-2;j++){
                if(j > i+1 && nums[j] == nums[j-1]) continue;
                int l = j+1, r = n-1;
                while(l < r){
                    long summ = (long)nums[i]+(long)nums[j]+(long)nums[l]+(long)nums[r];
                    if(summ == target){
                        anss.push_back({nums[i],nums[j],nums[l],nums[r]});
                        do {
                            l++;
                        }while(l > j+1 && l < n && nums[l] == nums[l-1]);
                    }
                    if(summ < target) l++;
                    if(summ > target) r--;
                }
            }
        }
        return anss;
    }
};