基本哈希问题
-
剑指 Offer 50. 第一个只出现一次的字符 - 力扣（LeetCode）;
class Solution { public: char firstUniqChar(string s) { char ans{' '}; unordered_map<char, int> st; for (auto c : s) ++st[c]; for (auto c : s) if (st[c] == 1) return c; return ans; } }; // 遍历哈希表的方法 class Solution { public: char firstUniqChar(string s) { char ans{' '}; unordered_map<char, int> st; int n = s.size(); for (int i{}; i < n; ++i) st[s[i]] = (st.count(s[i])) ? -1 : i; int idx{n}; for (auto [k, v] : st) if (~v && v < idx) ans = k, idx = v; return ans; } }; -
class Solution { public: int mostFrequentEven(vector<int>& nums) { unordered_map<int, int> cnt; for (auto i : nums) if (i % 2 == 0) ++cnt[i]; int ans{-1}, max_cnt{}; for (auto [k, v] : cnt) if (v > max_cnt || (v == max_cnt && ans > k)) max_cnt = v, ans = k; return ans; } }; -
class Solution { public: bool findSubarrays(vector<int>& nums) { int n = nums.size(); unordered_set<int> cnt{}; for (int i{1}; i < n; ++i) { if (cnt.count(nums[i - 1] + nums[i])) return true; cnt.insert(nums[i - 1] + nums[i]); } return false; } }; -
class Solution { public: vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) { unordered_map<int, int> dic{}; vector<vector<int>> ans{}; for (auto a : items1) dic[a[0]] += a[1]; for (auto b : items2) dic[b[0]] += b[1]; for (auto [k, v] : dic) ans.emplace_back(vector<int>{k, v}); sort(ans.begin(), ans.end()); return ans; } };或者用数组哈希:
class Solution { public: vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) { int dic[1001]{}; vector<vector<int>> ans{}; for (auto a : items1) dic[a[0]] += a[1]; for (auto b : items2) dic[b[0]] += b[1]; for (int i{}; i < 1001; ++i) if (dic[i]) ans.emplace_back(vector<int>{i, dic[i]}); return ans; } }; -
class Solution { public: bool isAnagram(string s, string t) { int cs[26]; memset(cs,0,26*sizeof(int)); for(int c1:s)cs[c1-'a']++; for(int c2:t)cs[c2-'a']--; for (int i{};i<26;++i)if(cs[i])return false; return true; } }; -
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> st; int n = nums.size(); for (int i{}; i < n; ++i) { if (st.find(nums[i]) != st.end()) return {st[nums[i]], i}; st[target - nums[i]] = i; } return {0, 0}; } }; -
1010. 总持续时间可被 60 整除的歌曲; (两数之和的进阶版, 需要考虑大数据范围下的操作, 其实就是$\%$操作, 很多降低时间复杂度方法都用到了这个操作)
class Solution { public: int numPairsDivisibleBy60(vector<int>& time) { unordered_map<int, int> cnt; int ans{}; for (auto i : time) { int tmp = (60 - i % 60) % 60; if (cnt.count(tmp)) ans += cnt[tmp]; ++cnt[i % 60]; } return ans; } }; // 数组哈希 class Solution { public: int numPairsDivisibleBy60(vector<int>& time) { int ans{}, cnt[60]{}; for (auto i : time) { int tmp = (60 - i % 60) % 60; if (cnt[tmp]) ans += cnt[tmp]; ++cnt[i % 60]; } return ans; } }; -
LCP 18. 早餐组合 - 力扣（LeetCode）;(类似两数之和)
// 或者数组哈希 class Solution { public: const int MOD = 1e9 + 7; int breakfastNumber(vector<int>& staple, vector<int>& drinks, int x) { int n = staple.size(); long long ans{}; int tmp[x + 1]; memset(tmp, 0, sizeof(tmp)); for (int st : staple) if (st < x) ++tmp[st]; for (int i{2}; i < x; ++i) tmp[i] += tmp[i - 1]; for (int dr : drinks) if (x - dr > 0) ans += tmp[x - dr]; return ans % MOD; } }; -
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> ans, n1(nums1.begin(), nums1.end()); for(int num : nums2) if(n1.find(num) != n1.end()) ans.insert(num); return vector<int>(ans.begin(), ans.end()); } }; -
219. 存在重复元素 II - 力扣（LeetCode）;
class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { int n = nums.size(), l{}; unordered_set<int> st; for (int r{}; r < n; ++r) { if (r > k) st.erase(nums[l++]); if (st.count(nums[r])) return true; st.insert(nums[r]); } return false; } }; -
$\bigstar$128. 最长连续序列 - 力扣（LeetCode）;
直观做法, 排序+遍历, 但是不是最快的.
class Solution { public: int longestConsecutive(vector<int> &nums) { sort(nums.begin(), nums.end()); int ans{}, n = nums.size(), tmp{1}; if (n < 2) return n; for (int i{1}; i < n; ++i) { if (nums[i] == nums[i - 1] + 1) tmp++; else if (nums[i] == nums[i - 1]) continue; else ans = max(ans, tmp), tmp = 1; } return max(ans, tmp); } };哈希做法: (很巧妙的方法, 找一段连续序列的最小值, 即左端点, 然后开始递增找最长的序列)
class Solution { public: int longestConsecutive(vector<int> &nums) { unordered_set<int> st(nums.begin(), nums.end()); int ans{}; for (const int &num : st) { if (st.count(num - 1)) continue; int cur = num, tmp = 1; while (st.count(cur + 1)) ++cur, ++tmp; ans = max(ans, tmp); } return ans; } }; -
1817. 查找用户活跃分钟数 - 力扣（LeetCode）;
class Solution { public: vector<int> findingUsersActiveMinutes(vector<vector<int>> &logs, int k) { unordered_map<int, unordered_set<int>> d; for (auto &log : logs) d[log[0]].insert(log[1]); vector<int> ans(k); for (auto &[_, ts] : d) ++ans[ts.size() - 1]; return ans; } }; -
1604. 警告一小时内使用相同员工卡大于等于三次的人 - 力扣（LeetCode）;
class Solution { public: vector<string> alertNames(vector<string> &keyName, vector<string> &keyTime) { vector<string> ans{}; unordered_map<string, vector<int>> dict{}; for (int i{}; i < keyName.size(); ++i) { string s{keyTime[i]}; int h = (s[0] - '0') * 10 + (s[1] - '0'); int m = (s[3] - '0') * 10 + (s[4] - '0'); dict[keyName[i]].emplace_back(h * 60 + m); } for (auto &[k, v] : dict) { int n = v.size(); if (n < 3) continue; sort(v.begin(), v.end()); int cnt{1}; for (int i{}; i < n - 2; ++i) { if (v[i + 2] - v[i] <= 60) { ans.emplace_back(k); break; } } } sort(ans.begin(), ans.end()); return ans; } }; -
1124. 表现良好的最长时间段 - 力扣（LeetCode）;
典型题, 需要用到前缀和, 然后讨论正负值情况, 正值可以直接放入结果中(因为肯定是最大的), 负值的讨论是一个难点, 需要考虑查找的元素为原索引减一, 这个可以画个图结合例子加深理解.
例如对于
[6,6,6,9,9]这个数组, 根据是否大于8转化成仅含有{1, -1}的序列:[-1, -1, -1, 1, 1], 前缀和数组(首元素设为零, 长度为原数组长度+1)为:[0, -1, -2, -3, -2, -1].那么这时候讨论的结果就是负值了, 需要考虑
-
矩阵上的哈希计数
-
2661. 找出叠涂元素;(需要记录每次涂色的行和列情况)
class Solution { public: int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(), N = arr.size(); vector<int> row(m), col(n); // row代表每一行的填充情况, col: 列 unordered_map<int, pair<int, int>> dic; // 先放好对应索引, 方便后续查找(并涂色) for (int i{}; i < m; ++i) for (int j{}; j < n; ++j) dic[mat[i][j]] = pair{i, j}; // 再开始遍历 arr 数组找满足条件的元素 for (int i{}; i < N; ++i) { int x = arr[i]; ++row[dic[x].first], ++col[dic[x].second]; if (row[dic[x].first] == n || col[dic[x].second] == m) return i; } return 0; } }; -
1072. 按列翻转得到最大值等行数; 需要考虑一个等价性, 即互补和全等
```cpp
class Solution {
public:
int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
unordered_map<string, int> cnt;
int ans{};
for (auto v : matrix) {
string s;
for (auto c : v) s.push_back('0' + (v[0] == 0 ? c : c ^ 1));
ans = max(ans, ++cnt[s]);
}
return ans;
}
};
```
原地哈希
解决重复数字/缺失数字问题
-
class Solution { public: int findRepeatNumber(vector<int>& nums) { int n = nums.size(); for(int i = 0; i < n; i++){ int k = nums[i]; // 拷贝一份值 if(k < 0) k += n; // 为了满足索引 if(nums[k] < 0) return k; // 遍历到负数 nums[k] -= n; // 标记 } return -1; } }; // +n取余标记 class Solution { public: int findRepeatNumber(vector<int>& nums) { int n = nums.size(); for(int i = 0; i < n; i++){ int k = nums[i] % n; // 拷贝一份值 if(nums[k] >= n) return k; // 遍历到 nums[k] += n; // 标记 } return -1; } };或者交换:
class Solution { public: int findRepeatNumber(vector<int>& nums) { int n = nums.size(), i{}; while (i < n) { // 关键: 找索引对应位置的元素 if (nums[i] == i) { // 已经放入对应位置 ++i; continue; } // 对应位置已经有元素了 if (nums[nums[i]] == nums[i]) return nums[i]; // 交换使得其中一个元素放入对应位置 swap(nums[i], nums[nums[i]]); } return -1; } }; -
442. 数组中重复的数据; ```cpp // 交换, 放入对应索引 class Solution { public: vector
findDuplicates(vector & nums) { int n = nums.size(); vector ans{}; for (int i{}; i < n; ++i) while (nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]); for (int i{}; i < n; ++i) if (nums[i] - 1 != i) ans.emplace_back(nums[i]); return ans; } };
// 一次遍历, 负号标记重复元素
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int n = nums.size();
vector<int> ans{};
for (int i{}; i < n; ++i) {
int x = nums[i];
if (x < 0) x = -x;
if (nums[x - 1] > 0)
nums[x - 1] = -nums[x - 1];
else
ans.emplace_back(x);
}
return ans;
}
};
// 通过取余, +n标记
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int n = nums.size();
vector<int> ans{};
for (int i{}; i < n; ++i) {
int x = (nums[i] - 1) % n;
if (nums[x] <= n)
nums[x] += n;
else
ans.emplace_back(x + 1);
}
return ans;
}
};
```
-
41. 缺失的第一个正数; ```cpp class Solution { public: int firstMissingPositive(vector
& nums) { int n = nums.size(), a; for (int& num : nums) // 先映射非正整数(n+1) if (num <= 0) num = n + 1; for (int& num : nums) // 标记正整数 if ((a = abs(num)) <= n) nums[a - 1] = -abs(nums[a - 1]); for (int i{}; i < n; ++i) // 看哪些下标没遍历过 if (nums[i] > 0) return i + 1; return n + 1; } }; ```
```cpp
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> ans{};
int n = nums.size();
for (int i{}; i < n; ++i)
while (nums[nums[i] - 1] != nums[i])
swap(nums[i], nums[nums[i] - 1]);
for (int i{}; i < n; ++i)
if (nums[i] != i + 1)
ans.emplace_back(i + 1);
return ans;
}
};
//
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
vector<int> ans{};
for (int num : nums) // 遍历过, 加上n作为标记
nums[(num - 1) % n] += n; // [1,n]->[n+1,XX]
for (int i{}; i < n; ++i)
if (nums[i] <= n)
ans.emplace_back(i + 1);
return ans;
}
};
```
设计哈希
哈希集合
基于 STL 的 vector
class MyHashSet {
vector<int> v{};
public:
MyHashSet() {}
void add(int key) {
if (!contains(key))
v.emplace_back(key);
}
void remove(int key) {
if (contains(key))
v.erase(std::remove(v.begin(), v.end(), key), v.end());
}
bool contains(int key) {
return find(v.begin(), v.end(), key) != v.end();
}
};
C-style 数组哈希: 空间换时间
class MyHashSet {
bool v[1000005]{}; // 需要囊括所有数据范围
public:
MyHashSet() {}
void add(int key) {
if (!contains(key))
v[key] = true;
}
void remove(int key) {
if (contains(key))
v[key] = false;
}
bool contains(int key) {
return v[key];
}
};
桶+位运算
用到的位运算:
x | (1 << b): 将x的(从低到高)第b位设为 1x & ~(1 << b): 将x的(从低到高)第b位设为 0(x >> b) & 1: 取出x的(从低到高)第b位
class MyHashSet {
int v[31251];
public:
MyHashSet() : v{} {}
void add(int key) {
int a = key / 32, b = key % 32;
v[a] = v[a] | (1 << b);
}
void remove(int key) {
int a = key / 32, b = key % 32;
v[a] = v[a] & ~(1 << b);
}
bool contains(int key) {
int a = key / 32, b = key % 32;
return ((v[a] >> b) & 1) == 1;
}
};
long 的优化版本:
class MyHashSet {
long v[15700];
const static int NUM = 64;
public:
MyHashSet(): v{} {}
void add(int key) {
int a = key / NUM, b = key % NUM;
v[a] = v[a] | (1L << b);
}
void remove(int key) {
int a = key / NUM, b = key % NUM;
v[a] = v[a] & ~(1L << b);
}
bool contains(int key) {
int a = key / NUM, b = key % NUM;
return ((v[a] >> b) & 1L) == 1;
}
};
最快的方法: 哈希取模+拉链法
class MyHashSet {
private:
static const int base = 769; // 最合适的基数
vector<list<int>> data; // 开链法
static int hash(int key) {
return key % base;
}
public:
MyHashSet() : data(base) {}
void add(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it) == key) {
return;
}
}
data[h].push_back(key);
}
void remove(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it) == key) {
data[h].erase(it);
return;
}
}
}
bool contains(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it) == key) {
return true;
}
}
return false;
}
};
哈希映射(map)
朴实无华数组哈希(巨慢)
class MyHashMap {
int v[1000001][2]{};
public:
MyHashMap() {}
void put(int key, int value) {
v[key][0] = 1, v[key][1] = value;
}
int get(int key) {
return v[key][0] ? v[key][1] : -1;
}
void remove(int key) {
v[key][0] = 0;
}
};
哈希取模:
class MyHashMap {
private:
static const int base = 769;
vector<list<pair<int, int>>> data;
static int hash(int key) { return key % base; }
public:
MyHashMap() : data(base) {}
void put(int key, int value) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); ++it)
if (it->first == key) {
it->second = value;
return;
}
data[h].push_back({key, value});
}
int get(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); ++it)
if (it->first == key) return it->second;
return -1;
}
void remove(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); ++it)
if (it->first == key) {
data[h].remove(*it);
return;
}
}
};
前缀和+哈希
需要好好思考一下, 特别是存入哈希的时机和更新结果的时机.
哈希表意味着什么? 本质上是两数之和操作, 两数之和需要的是找另一个能与当前值相加得到目标值的一个数, 这个数可能遍历过(存入哈希), 所以每次都更新然后去哈希表里面找就行了.
这类题目也是一样道理, 只不过这次用的是前缀和来找满足条件的另一个值(子数组的左端点), 当前遍历的值是子数组的右端点, 所以这才能使用哈希表简化运算.
遇到一些需要取模操作的题目, 需要动手推导一下, 没准只是用到了一些二级结论或者简单的移项合并等操作, 时间复杂度就减少了一个量级, 而这不是直接想就能想出来的(对我来说).
-
1590. 使数组和能被 P 整除 - 力扣（LeetCode）;(关键是取模操作, 降低数据复杂度)
class Solution { public: int minSubarray(vector<int> &nums, int p) { int n = nums.size(), ans{n}, presum[n + 1]; presum[0] = 0; for (int i{}; i < n; ++i) presum[i + 1] = (presum[i] + nums[i]) % p; unordered_map<int, int> cnt; // presum[l] : index of l int sum = presum[n]; for (int i{}; i <= n; ++i) { cnt[presum[i]] = i; int tmp = (presum[i] - sum + p) % p; if (cnt.count(tmp)) ans = min(ans, i - cnt[tmp]); } return ans == n ? -1 : ans; } }; -
560. 和为 K 的子数组; (计数类问题需要先更新结果再更新哈希表, 否则会多记录边界值)
class Solution { public: int subarraySum(vector<int>& nums, int k) { int n = nums.size(), ans{}, presum[n + 1]; presum[0] = 0; for (int i{}; i < n; ++i) presum[i + 1] = presum[i] + nums[i]; unordered_map<int, int> cnt; for (int i{}; i <= n; ++i) { auto it = cnt.find(presum[i]); if (it != cnt.end()) ans += it->second; ++cnt[presum[i] + k]; } return ans; } }; -
974. 和可被 K 整除的子数组;
cpp class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { int n = nums.size(), presum[n + 1], ans{}; presum[0] = 0; for (int i{}; i < n; ++i) presum[i + 1] = (presum[i] + nums[i]) % k; unordered_map<int, int> cnt; for (int i{}; i <= n; ++i) { ans += cnt[(presum[i] + k) % k]; ++cnt[(presum[i] + k) % k]; } return ans; } }; -
523. 连续的子数组和;(因为需要保证长度大等 2, 这就需要让遍历找的值为
i-2)
```cpp
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int n = nums.size(), presum[n + 1];
presum[0] = 0;
for (int i{}; i < n; ++i)
presum[i + 1] = presum[i] + nums[i];
unordered_set<int> st;
for (int i{2}; i <= n; ++i) {
st.insert(presum[i - 2] % k);
if (st.count(presum[i] % k))
return true;
}
return false;
}
};
```
-
525. 连续数组; (注意用 1 和-1 处理不同情况)
class Solution { public: int findMaxLength(vector<int>& nums) { int n = nums.size(), presum[n + 1], ans{}; presum[0] = 0; for (int i{}; i < n; ++i) presum[i + 1] = presum[i] + (nums[i] ? nums[i] : -1); // 0 -> -1 unordered_map<int, int> cnt; for (int i{}; i <= n; ++i) { if (cnt.count(presum[i])) ans = max(ans, i - cnt[presum[i]]); else cnt[presum[i]] = i; } return ans; } }; -
面试题 17.05. 字母与数字;( 和上一个题异曲同工)
cpp class Solution { public: vector<string> findLongestSubarray(vector<string>& array) { int n = array.size(), presum[n + 1], len{}, start{}; presum[0] = 0; for (int i{}; i < n; ++i) presum[i + 1] = presum[i] + (isdigit(array[i][0]) ? 1 : -1); unordered_map<int, int> cnt; for (int i{}; i <= n; ++i) { if (cnt.count(presum[i])) { if (i - cnt[presum[i]] > len) len = i - cnt[presum[i]], start = cnt[presum[i]]; } else cnt[presum[i]] = i; } return vector<string>(array.begin() + start, array.begin() + len + start); } };
数对问题
-
1512. 好数对的数目 - 力扣（LeetCode）;(直接哈希存值)
class Solution { public: int numIdenticalPairs(vector<int> &nums) { unordered_map<int, int> cnt{}; for (int num : nums) cnt[num]++; int ans{}; for (auto [_, v] : cnt) ans += v * (v - 1) / 2; return ans; } }; -
2342. 数位和相等数对的最大和 - 力扣（LeetCode）;
class Solution { public: int f(int n) { int ans{}; while (n) ans += n % 10, n /= 10; return ans; } int maximumSum(vector<int>& nums) { unordered_map<int, int> cnt{}; int ans{}, tmp{}; for (int num : nums) { tmp = f(num); if (cnt[tmp]) ans = max(ans, num + cnt[tmp]); cnt[tmp] = max(num, cnt[tmp]); } return ans == 0 ? -1 : ans; } }; -
面试题 16.24. 数对和 - 力扣（LeetCode）;(哈希可以做, 但是双指针更快, 有点像三数之和)
class Solution { public: vector<vector<int>> pairSums(vector<int>& nums, int target) { unordered_map<int, int> cnt{}; vector<vector<int>> ans; for (int num : nums) { int t = target - num; if (cnt[t]) { ans.emplace_back(vector<int>{num, t}); cnt[t]--; } else cnt[num]++; } return ans; } };双指针:
基于哈希的数据结构
-
1797. 设计一个验证系统 - 力扣（LeetCode）;
class AuthenticationManager { int ttl; unordered_map<string, int> dic; public: AuthenticationManager(int timeToLive) { ttl = timeToLive; } void generate(string tokenId, int currentTime) { dic[tokenId] = currentTime; } void renew(string tokenId, int currentTime) { if (dic.find(tokenId) != dic.end() && dic[tokenId] + ttl > currentTime) dic[tokenId] = currentTime; } int countUnexpiredTokens(int currentTime) { int ans{}; for (auto& [_, ct] : dic) ans += (ct + ttl > currentTime); return ans; } };
有序集合
-
剑指 Offer 41. 数据流中的中位数;295. 数据流的中位数;(有序集合)
class MedianFinder { multiset<int> nums; multiset<int>::iterator l, r; public: MedianFinder() : l(nums.end()), r(nums.end()) {} void addNum(int num) { int n = nums.size(); nums.insert(num); if (!n) // 空 l = r = nums.begin(); else if (n & 1) { // 奇数 if (num < *l) --l; else ++r; } else { // 偶数 if (num > *l && num < *r) ++l, --r; else if (num >= *r) ++l; else --r, l = r; } } double findMedian() { return (*l + *r) / 2.0; } };