算法训练day7: LeetCode454.383.15.18
454.四数相加
题目
题解
-
class Solution { public: int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4) { unordered_map<int, int> umap; // key存数值,value存出现次数 for (int a : nums1) { for (int b : nums2) { umap[a + b]++; } } int count = 0; for (int c : nums3) { for (int d : nums4) { if (umap.find(0 - (c + d)) != umap.end()) { count += umap[0 - (c + d)]; } } } return count; } };
刚看没什么想法,后来意识到和昨天的那道题类似。
383.赎金信
题目
题解
-
因为只有26个小写字母,使用数组哈希表。
-
还有目标串比来源串长的情况
-
class Solution { public: bool canConstruct(string ransomNote, string magazine) { int Hash[26] = {0}; if (ransomNote.size() > magazine.size()) { return false; } for (int i = 0; i < magazine.size(); i++) { Hash[magazine[i] - 'a']++; } for (int j = 0; j < ransomNote.size(); j++) { Hash[ransomNote[j] - 'a']--; if (Hash[ransomNote[j] - 'a'] < 0) { return false; } } return true; } };