C++ 哈希表
目录
两数之和
面试题 01.02. 判定是否互为字符重排
存在重复元素
存在重复元素 II
字母异位词分组
两数之和
1. 两数之和
思路1：两层for循环
思路2：逐步添加哈希表
思路3：一次填完哈希表
如果一次填完，那么相同元素的值，所映射的下标是最后一个的，然而并不会导致代码出问题，不管 i 是正向还是反向遍历，原因1：只需要能找到num的下标就行；2：对于num = target / 2 时 ，当前元素不影响，说结果就是这里的覆盖并不影响，因为思路2也是会覆盖掉之前出现过的元素
细节：当前下标不能和 hash[num] 相同 反例：{1 ，3， 4} target = 6，也就是当前元素只有一个，且为 target / 2这时候可能出错
参考代码2
class Solution1 {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;hash[nums[0]] = 0;for (int i = 1; i < nums.size(); i++){int num = target - nums[i];if (hash.count(num)) return { hash[num], i };hash[nums[i]] = i;}return { -1, -1 };}
};参考代码3
class Solution1 {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;int n = nums.size();for (int i = 0; i < n; i++)hash[nums[i]] = i;//for (int i = 0; i < n; i++)for (int i = n - 1; i >= 0; i--){int num = target - nums[i];if (hash.count(num) && hash[num] != i)return { i, hash[num] };}return { -1, -1 };}
};面试题 01.02. 判定是否互为字符重排
面试题 01.02. 判定是否互为字符重排
思路1：两个数组，一个去比较另一个
思路2：一个数组，去比较0
思路3：sort排序string， sort要求是的一个可以下标随机访问的容器，string重载了[]
参考代码 两个数组
class Solution {
public:bool CheckPermutation(string s1, string s2) {if (s1.size() != s2.size()) return false;int hash1[26] = { 0 }, hash2[26] = { 0 };for (auto e : s1)hash1[e - 'a']++;for (auto e : s2)hash2[e - 'a']++;for (int i = 0; i < 26; i++)if (hash1[i] != hash2[i])return false;return true;}
};一个数组
class Solution {
public:bool CheckPermutation(string s1, string s2) {if (s1.size() != s2.size()) return false;int hash[26] = { 0 };for (auto e : s1)hash[e - 'a']++;for (auto e : s2)//也可以在里面判断hash[e - 'a']--;for (int i = 0; i < 26; i++)if (hash[i] < 0) return false;return true;}
};sort
class Solution {
public:bool CheckPermutation(string s1, string s2) {if (s1.size() != s2.size()) return false;sort(s1.begin(), s1.end());sort(s2.begin(), s2.end());return s1 == s2;}
};存在重复元素
217. 存在重复元素
参考代码
class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_map<int, int> hash;for (auto e : nums)if (hash.count(e)) return true;else hash[e]++;return false;}
};存在重复元素 II
219. 存在重复元素 II
参考代码
class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> hash;for(int i = 0; i < nums.size(); i++){if(hash.count(nums[i]) && hash[nums[i]] + k >= i) return true;hash[nums[i]] = i;}return false;}
};字母异位词分组
49. 字母异位词分组
对于往ret里压数据，是参考资料的，原来是这么想的，但是不对，hash只会用一点，还没学。。
参考代码
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;for(auto e : strs){string tmp = e;sort(tmp.begin(), tmp.end());hash[tmp].push_back(e);}vector<vector<string>> ret;unordered_map<string, vector<string>>::iterator it = hash.begin();while (it != hash.end()){ret.push_back(it->second);++it;}return ret;}
};