代码随想录-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;     } };