代码随想录-DAY⑥-哈希表——leetcode 383 | 454

383

思路

首先统计 magazine 中每个英文字母 a 的次数 cnt[a]，再遍历统计 ransomNote 中每个英文字母的次数，如果发现 ransomNote 中存在某个英文字母 c 的统计次数大于 magazine 中该字母统计次数 cnt[c]，则此时我们直接返回 false。

时间复杂度：O(n+m)
空间复杂度：O(1)

代码

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> cnt(26);
        for (auto c : magazine) {
            cnt[c - 'a']++;
        }
        for (auto c : ransomNote) {
            cnt[c - 'a']--;
            if (cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

454

思路

将四个数组分成两部分，A 和 B 为一组，C 和 D 为另外一组。
遍历A和B数组，统计两个数组元素之和，和出现的次数，放到map中。
定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
再遍历C和D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。

时间复杂度：O(n^2)
空间复杂度：O(n^2)

代码

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap;
        int count = 0;
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;
            }
        }
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};