Hash Table 基础
哈希表 (Hash Table) 是常用的数据结构, 其运用哈希函数 (hash function) 实现映射, 内部使用开放定址, 拉链法等方式解决哈希冲突, 使得读写时间复杂度平均为 O(1).
HashMap(std::unordered_map),HashSet(std::unordered_set)的原理与 Hash Table 一样, 它们的用途广泛, 用法灵活, 接下来侧重于介绍它们的应用.
相关 LeetCode 题:
706. Design HashMap https://leetcode.com/problems/design-hashmap/ 题解
705. Design HashSet https://leetcode.com/problems/design-hashset/ 题解
集合
如果仅需要判断元素是否存在于某个集合, 我们可以使用结构 HashSet(std::unordered_set). 例如 LeetCode 题目 349. Intersection of Two Arrays:
- // 349. Intersection of Two Arrays
- vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
- unordered_set<int> s1(nums1.begin(),nums1.end());
- unordered_set<int> s2(nums2.begin(),nums2.end());
- vector<int> res;
- for(auto& a:s1)
- if(s2.count(a)) res.push_back(a);
- return res;
- }
相关 LeetCode 题:
349. Intersection of Two Arrays 题解
771. Jewels and Stones https://leetcode.com/problems/jewels-and-stones/ 题解
202. Happy Number https://leetcode.com/problems/happy-number/ 题解
166. Fraction to Recurring Decimal 题解
720. Longest Word in Dictionary 题解
970. Powerful Integers https://leetcode.com/problems/powerful-integers/ 题解
204. Count Primes https://leetcode.com/problems/count-primes/ 题解
36. Valid Sudoku https://leetcode.com/problems/valid-sudoku/ 题解
计数
如果需要对元素进行计数, 我们可以使用结构 HashMap(std::unordered_map), 元素如取值范围固定可以用 Array(std::vector), 例如 LeetCode 题目 217. Contains Duplicate:
- // 217. Contains Duplicate
- bool containsDuplicate(vector<int>& nums) {
- unordered_map<int,int> m;
- for(int x:nums) if(m[x]++==1) return true;
- return false;
- }
相关 LeetCode 题:
217. Contains Duplicate https://leetcode.com/problems/contains-duplicate/ 题解
811. Subdomain Visit Count 题解
1002. Find Common Characters 题解
266. Palindrome Permutation 题解
242. Valid Anagram https://leetcode.com/problems/valid-anagram/ 题解
748. Shortest Completing Word 题解
1072. Flip Columns For Maximum Number of Equal Rows 题解
451. Sort Characters By Frequency 题解
347. Top K Frequent Elements 题解
454. 4Sum II https://leetcode.com/problems/4sum-ii/ 题解
781. Rabbits in Forest https://leetcode.com/problems/rabbits-in-forest/ 题解
30. Substring with Concatenation of All Words 题解
在滑动窗口算法中常使用 HashMap 计数, 关于滑动窗口算法, 详见: 算法与数据结构基础 - 滑动窗口(Sliding Windows)
Key-Val
进一步地, HashMap 表示一种 Key-Val (或 ID - 属性) 关系, 这里 Val 可以是计数, 下标 (index) 等等.
相关 LeetCode 题:
1. Two Sum https://leetcode.com/problems/two-sum/ 题解
219. Contains Duplicate II 题解
953. Verifying an Alien Dictionary 题解
359. Logger Rate Limiter https://leetcode.com/problems/logger-rate-limiter/ 题解
1086. High Five https://leetcode.com/problems/high-five/ 题解
690. Employee Importance https://leetcode.com/problems/employee-importance/ 题解
981. Time Based Key-Value Store 题解
325. Maximum Size Subarray Sum Equals k 题解
244. Shortest Word Distance II 题解
355. Design Twitter https://leetcode.com/problems/design-twitter/ 题解
336. Palindrome Pairs https://leetcode.com/problems/palindrome-pairs/ 题解
映射
更一般地, HashMap 表示一种映射关系, 意义在于 O(1)时间复杂度完成由 A->B 的映射.
相关 LeetCode 题:
246. Strobogrammatic Number 题解
205. Isomorphic Strings https://leetcode.com/problems/isomorphic-strings/ 题解
49. Group Anagrams https://leetcode.com/problems/group-anagrams/ 题解
249. Group Shifted Strings 题解
290. Word Pattern https://leetcode.com/problems/word-pattern/ 题解
138. Copy List with Random Pointer 题解
535. Encode and Decode TinyURL 题解
710. Random Pick with Blacklist 题解
HashMap 与 Prefix sum
利用 HashMap 和 Prefix sum, 我们可以在 O(n)时间复杂度求解一类子序列求和问题, 其中 HashMap 用于计数, 例如 LeetCode 题目 560. Subarray Sum Equals K:
- // 560. Subarray Sum Equals K
- int subarraySum(vector<int>& nums, int k) {
- unordered_map<int,int> m;
- m[0]=1;
- int sum=0,res=0;
- for(auto& a:nums){
- sum+=a;
- res+=m[sum-k];
- m[sum]++;
- }
- return res;
- }
相关 LeetCode 题:
560. Subarray Sum Equals K 题解
525. Contiguous Array https://leetcode.com/problems/contiguous-array/ 题解
930. Binary Subarrays With Sum 题解
325. Maximum Size Subarray Sum Equals k 题解
554. Brick Wall https://leetcode.com/problems/brick-wall/ 题解
HashMap 与图形问题
HashMap 可以应用于二维图形的一些问题求解, 以欧拉距离, 斜率, x/y 坐标等为 key, 以计数, x/y 坐标为 val. 图形问题中 HashMap 的映射关系不是那么直观和明显, 需要单独计算 key, 仔细甄别映射关系.
相关 LeetCode 题:
447. Number of Boomerangs 题解
939. Minimum Area Rectangle 题解
149. Max Points on a Line 题解
356. Line Reflection https://leetcode.com/problems/line-reflection/ 题解
HashMap 与 vector/list/stack 结合
HashMap 与 vector,list,stack 等数据结构可以结合成为复合数据结构, 这样可以既用到 HashMap O(1)的优点, 也用到 vector 支持下标操作, list 增删节点快, stack 先进后出的特点. 例如 LeetCode 题目 380. Insert Delete GetRandom O(1):
- // 380. Insert Delete GetRandom O(1)
- vector<int> v;
- unordered_map<int,int> m;
以上用 vector 存储元素, unordered_map 存储元素和对应下标; getRandom 函数利用 vector 下标操作, 而删除元素时, 使用 unordered_map 取得被删元素, 将 vector 末尾元素与其对调, 利用了 HashMap O(1)的优点.
相关 LeetCode 题:
380. Insert Delete GetRandom O(1) 题解
381. Insert Delete GetRandom O(1) - Duplicates allowed 题解
895. Maximum Frequency Stack 题解
146. LRU Cache https://leetcode.com/problems/lru-cache/ 题解
来源: https://www.cnblogs.com/bangerlee/p/11284422.html