跟着《代码随想录》刷题（三）——哈希表

3.1 哈希表理论基础

哈希表理论基础

3.2 有效的字母异位词

242.有效的字母异位词

C

bool isAnagram(char * s, char * t){int array[26] = {0};int i = 0;while (s[i]) {// 并不需要记住字符的ASCII码，只需要求出一个相对数值就可以了array[s[i] - 'a']++;i++;}i = 0;while (t[i]) {array[t[i] - 'a']--;i++;}for (i = 0; i < 26; i++) {// 如果数组有元素不为0，说明字符串s和t 一定是谁多了字符或者谁少了字符if (array[i] != 0)return false;}// 数组所有元素都为0，说明字符串s和t是字母异位词return true;
}

cpp

class Solution {
public:bool isAnagram(string s, string t) {int array[26] = {0};for (int i = 0; i < s.size(); i++) {array[s[i] - 'a']++;}for (int j = 0; j < t.size(); j++) {array[t[j] - 'a']--;}for (int k = 0; k < 26; k++) {if (array[k] != 0) {return false;}}return true;}
};

383.赎金信

c

bool canConstruct(char * ransomNote, char * magazine){int array[26] = {0};if (strlen(ransomNote) > strlen(magazine)) return false;int i = 0;while (magazine[i]) {array[magazine[i] - 'a']++;i++;}i = 0;while(ransomNote[i]) {array[ransomNote[i] - 'a']--;if (array[ransomNote[i] - 'a'] < 0)return false;i++;}return true;
}

cpp

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

49. 字母异位词分组

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vector<string>> result;unordered_map<string, vector<string>> map;for (string &s : strs) {string key = s;sort(key.begin(), key.end());map[key].emplace_back(s);}for (auto &it : map) result.emplace_back(it.second);return result;}
};

438. 找到字符串中所有字母异位词（滑动窗口+哈希）

class Solution {
public:vector<int> findAnagrams(string s, string p) {int len_s = s.length();int len_p = p.length();if (len_s < len_p)return vector<int> ();vector<int> count_s(26);vector<int> count_p(26);vector<int> res;for (int i = 0; i < len_p; i++) {count_s[s[i] - 'a']++;count_p[p[i] - 'a']++;}if (count_s == count_p)res.push_back(0);for (int j = 0; j < len_s - len_p; j++) {count_s[s[j] - 'a']--;count_s[s[j + len_p] - 'a']++;if (count_s == count_p)res.push_back(j + 1); // 注意：这里左边已经移动了一位了，所以要加1}return res;}
};

3.3 两个数组的交集

349. 两个数组的交集

c语言

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int lessSize = nums1Size < nums2Size ? nums1Size : nums2Size;// 用calloc直接全部初始化为0，malloc则是随机值int *res = calloc(lessSize, sizeof(int));int hash[1001] = {0};for (int i = 0; i < nums1Size; i++) {hash[nums1[i]]++;}int count = 0;for (int j = 0; j < nums2Size; j++) {if (hash[nums2[j]] > 0) {res[count++] = nums2[j];}hash[nums2[j]] = 0;}*returnSize = count;return res;
}

cpp
解法一：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result;// 存放结果，之所以用unordered_set，是为了给结果去重unordered_set<int> set(nums1.begin(), nums1.end());for (int num : nums2) {// 发现nums2中的结果在set中出现过if (set.find(num) != set.end()) {result.insert(num);}}return vector<int> (result.begin(), result.end());}
};

解法二：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result;int hash[1001] = {0};for (int n1 : nums1) {hash[n1] = 1;}for (int n2 : nums2) {if (hash[n2] == 1) {result.insert(n2);}}return vector<int>(result.begin(), result.end());}
};

350. 两个数组的交集||

C语言

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int lessSize = nums1Size < nums2Size ? nums1Size : nums2Size;int* ret = calloc(lessSize, sizeof(int));int hash[1001] = {0};int count = 0;int i;for (i = 0; i < nums1Size; i++) {hash[nums1[i]]++;}for (i = 0; i < nums2Size; i++) {if (hash[nums2[i]] > 0) {ret[count++] = nums2[i];hash[nums2[i]]--;}}*returnSize = count;return ret;
}

C++

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int> num_map;for (int n1 : nums1) {num_map[n1]++;}vector<int> res;for (int num : nums2) {if (num_map.count(num)) {res.push_back(num);num_map[num]--; if (num_map[num] == 0) {num_map.erase(num);}}}return res;}
};

3.4 快乐数（unordered_set）

202. 快乐数

class Solution {
public:int getSum(int n) {int sum = 0;while (n) {sum += (n % 10) * (n % 10);n /= 10;}return sum;}bool isHappy(int n) {if (1 == n)return true;unordered_set<int> sum_set;int sum = 0;while (1) {sum = getSum(n);if (1 == sum)return true;// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return falseif (sum_set.find(sum) != sum_set.end()) {return false;} else {sum_set.insert(sum);n = sum;}}}
};

3.5 两数之和（unorderd_map)

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++) {int s = target - nums[i];auto iter = map.find(s);// 遍历当前元素，并在map中寻找是否有匹配的keyif (iter != map.end()) {return {iter->second, i};} else {// 如果没找到匹配对，就把访问过的元素和下标加入到map中map.insert(pair<int, int>(nums[i], i));}}return {};}
};

3.6 四数相加||

454. 四数相加||

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> map; //key:a+b的数值，value:a+b数值出现的次数int target = 0;int count = 0;// 统计a+b+c+d = 0 出现的次数// 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中for (int a : nums1) {for (int b : nums2)map[a + b]++;}// 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，//就把map中key对应的value也就是出现次数统计出来。for (int c : nums3) {for (int d : nums4) {target = 0 - (c + d);if (map.find(target) != map.end()) {count += map[target];}}}return count;}
};

3.7 赎金信

383.赎金信

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {if (ransomNote.length() > magazine.length()) return false;int array[26] = {0};for (char s1 : magazine) {array[s1 - 'a']++;}for (char s2 : ransomNote) {array[s2 - 'a']--;if (array[s2 - 'a'] < 0)return false;}return true;}
};

3.8 三数之和

15.三数之和

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(), nums.end());// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了for (int i = 0; i < nums.size(); i++) {if (nums[i] > 0) return res;// 正确去重a方法if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1;int right = nums.size() - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) right--;else if (sum < 0)left++;else {res.push_back(vector<int>{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重while (left < right && nums[right] == nums[right - 1])right--;while (left < right && nums[left] == nums[left + 1])left++;// 找到答案时，双指针同时收缩right--;left++;}}}return res;}
};

3.9 四数之和

18. 四数之和

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> res;sort(nums.begin(), nums.end());// 一级剪枝for (int k = 0; k < nums.size(); k++) {if (nums[k] > target && nums[k] >=0)break; // 这里使用break，统一通过最后的return返回// 一级去重，对nums[k]去重if (k > 0 && nums[k] == nums[k - 1])continue;for (int i = k + 1; i < nums.size(); i++) {// 二级剪枝if (nums[k] + nums[i] > target && nums[k] + nums[i] >=0)break;// 二级去重，对nums[i]去重if (i > k + 1 && nums[i] == nums[i - 1])continue;int left = i + 1;int right = nums.size() - 1;while (left < right) {// 会溢出long sum = (long)nums[k] + nums[i] + nums[left] + nums[right];if (sum > target)right--;else if (sum < target)left++;else {res.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});// 对nums[left]和nums[right]去重while (left < right && nums[right] == nums[right - 1])right--;while (left < right && nums[left] == nums[left + 1])left++;// 找到答案时，双指针同时收缩right--;left++;}}}}return res;}
};

参考：《代码随想录》哈希表