【数据结构与算法】LeetCode：哈希表

哈希表

一般查找 (键查找)

两数之和 (Hot 100)

两数之和

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> map;  // <数值,下标>for(int i = 0; i < nums.size(); i++){     // 对于每个数字nums[i]auto it = map.find(target - nums[i]);  // 查找target - nums[i]if(it != map.end()){ return {it->second, i};  // {target - nums[i]的索引，nums[i]的索引}}map[nums[i]] = i;   }return {};}
};

两个数组的交集

两个数组的交集

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result;// num1的元素集合unordered_set<int> nums1_set(nums1.begin(), nums1.end());for(auto num:nums2){  // 找出nums2在nums1中出现的元素if (nums1_set.count(num)){result.insert(num);}}return vector<int>(result.begin(), result.end());}
};

快乐数

快乐数

class Solution {
public:// 计算一个数的各位数字的平方和  int getSquareSum(int n) {  int sum = 0;  while (n > 0) {  int digit = n % 10; sum += digit * digit;n /= 10;}  return sum;  }  // 判断一个数是否为快乐数  bool isHappy(int n) {  std::unordered_set<int> seen;     // 使用集合来存储已经出现过的数  while (n != 1 && !seen.count(n)){ // 当 n 不为 1 且 n 没有出现过时  seen.insert(n);               n = getSquareSum(n);          }  return n == 1;                    // 如果 n 最终为 1，则为快乐数}    
};

环形链表 （Hot 100）

环形链表

class Solution {
public:bool hasCycle(ListNode *head) {unordered_set<ListNode*> visited;ListNode * cur = head;while (cur != nullptr) {if (visited.count(cur)) {return true;}visited.insert(cur);cur = cur->next;}return false;}
};

环形链表 II （Hot 100）

环形链表 II

class Solution {
public:ListNode *detectCycle(ListNode *head) {unordered_set<ListNode *> visited;ListNode* cur = head;while (cur != nullptr) {// 遍历链表中的每个节点，并将它记录下来if (visited.count(cur)) { // 一旦遇到了此前遍历过的节点，就可以判定链表中存在环。return cur;}visited.insert(cur);cur = cur->next;}return nullptr;}
};

和为 K 的子数组 (Hot 100)

和为 K 的子数组

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int ans = 0;int pre = 0; // 前缀和，子数组[num[j]..num[i]] 和为k 即 pre[i]−pre[j−1]==kunordered_map<int, int> map_pre_num; // 存储每个前缀和出现的次数。map_pre_num[0] = 1;for (auto& num : nums) {pre += num; // 计算前缀和// 判断是否已存在pre - k的前缀和，// 如果存在，说明之前有map_pre_num[pre - k]个位置到当前位置的连续子数组的和为kif (map_pre_num.find(pre - k) != map_pre_num.end()) {ans += map_pre_num[pre - k];}map_pre_num[pre]++;}return ans;}
};

计数查找 (值查找)

有效的字母异位词

有效的字母异位词（计数对象可数）

class Solution {
public:bool isAnagram(string s, string t) {// 使用哈希表来统计两个字符串各个字符出现次数的差值。// 如果差值都为0，则为字母异位词 // map需要更多的开销，因此优先使用数组vector<int>vec(26,0);for(auto c: s) vec[c - 'a']++;for(auto c: t) vec[c - 'a']--;// 查找数量不同的字母，有则表示s和t不是字母异位词for (auto t: vec){  if(t!=0) return false;}return true;}
};

字符串中的第一个唯一字符

字符串中的第一个唯一字符（计数对象可数）：

class Solution {
public:int firstUniqChar(string s) {std::unordered_map<char, int> map; // 统计每个字符的出现次数  for (char c : s) map[c]++;// 遍历字符串，找到第一个只出现一次的字符  for (int i = 0; i < s.size(); i++) {  if (map[s[i]] == 1) return i;   }  return -1; }};

只出现一次的数字 (Hot 100)

只出现一次的数字（计数对象不可数）：

class Solution {
public:int singleNumber(vector<int>& nums) {unordered_map<int, int> map;// 统计每个字符的出现次数  for (int num : nums) {  map[num]++;  }  // 查找只出现一次的元素for(auto item: map){if(item.second == 1) return item.first;}return NULL;}
};

多数元素

多数元素

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int, int> counts;int ans = 0, max_count = 0;for (int num: nums) {counts[num]++;if (counts[num] > max_count) { // 查找最多的数ans = num;max_count = counts[num];}}return ans;}
};

键、值查找

两个数组的交集 II

两个数组的交集 II

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {  unordered_map<int, int> map;  vector<int> result;  // 元素可重复// 记录nums1每个元素出现的次数  for (int num : nums1) map[num]++;   // 遍历 nums2，如果元素在哈希表中且计数大于零，则添加到结果集中并减少计数  // 第一个条件（键）：检查 num 是否存在于哈希表 map 中// 第二个条件（值）：确保只将在 nums1 中出现过（即计数大于零）的元素添加到结果集中，for (int num : nums2) {  if (map.find(num) != map.end() && map[num] > 0) {  result.push_back(num);  map[num]--;  // 确保各个元素添加的次数不超过它们在 nums1 中出现次数}  }  return result;  }  
};

其他

字母异位词分组

字母异位词分组

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> mp;//  不同词排序后的字母集是相同的，设为键。字母组成相同的词设为值。for (string& str: strs) {string key = str;sort(key.begin(), key.end()); // 字母集mp[key].emplace_back(str);    // <字母集,词>}vector<vector<string>> ans;for (auto it: mp) {ans.emplace_back(it.second);}return ans;}
};

最长连续序列

最长连续序列

class Solution{
public:int longestConsecutive(vector<int>& nums){unordered_set<int> set;for(auto num:nums) set.insert(num);int max_length = 0;for(auto num: set){if(!set.count(num - 1)){ // 最长连续序列的开头值（最小值）xint cur_length = 1; // 以x为起点，不断尝试匹配 x+1,x+2,⋯ 是否存在while(set.count(num+1)){num++;cur_length++;} max_length = max(max_length, cur_length);}}return max_length;}
};

LRU 缓存 (Hot 100)

LRU 缓存

struct DlinkedNode{int key, value;DlinkedNode* prev;DlinkedNode* next;DlinkedNode(int _key = 0, int _value = 0 ): key(_key),value(_value), prev(nullptr),next(nullptr){};
};
class LRUCache {
private:unordered_map<int, DlinkedNode*> cache;DlinkedNode* head; // 伪头DlinkedNode* tail; // 伪尾int size = 0;     // 当前缓存的节点数量int capacity;     // 容量
public:LRUCache(int _capacity):capacity(_capacity) {// 伪头部和伪尾部节点head = new DlinkedNode();tail = new DlinkedNode();head->next = tail;tail->prev = head;}~LRUCache() {  // 析构函数，清理资源  DlinkedNode* curr = head->next;  while (curr != tail) {  DlinkedNode* temp = curr;  curr = curr->next;  delete temp;  }  delete head;  delete tail; } void put(int key, int value) {// 如果关键字 key 不存在，则向缓存中插入该组 key-value 。// 如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。if(!cache.count(key)){DlinkedNode* node = new DlinkedNode(key, value);cache[key] = node;addToHead(node);size++;if(size > capacity) removeTail();}else{ // 如果关键字 key 已经存在，则变更其数据值 value,并移动到头部DlinkedNode* node = cache[key];node->value = value;addToHead(node, true);}}int get(int key) {if(!cache.count(key)) return -1; // key不存在// 如果 key 存在，先通过哈希表定位，再移到头部DlinkedNode* node = cache[key];addToHead(node, true);// 尾部是最久未使用return node->value;}void addToHead(DlinkedNode* node, bool exit = false){if(exit){node->prev->next = node->next;node->next->prev = node->prev;}node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}void removeTail(){DlinkedNode* node = tail->prev;node->prev->next = node->next;node->next->prev = node->prev;// 删除哈希表中对应的项cache.erase(node->key);delete node;size--;}
};

复制带随机指针的链表

复制带随机指针的链表

class Solution {
public:Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;Node* cur = head;unordered_map<Node*, Node*> map; // <原节点，复制的新节点>// 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射while(cur != nullptr) {Node* new_node =  new Node(cur->val);map[cur] = new_node; // 原节点 -> 新节点cur = cur->next;}cur = head;// 构建新链表的 next 和 random 指向while(cur != nullptr) {// 值为新节点，键为旧节点// 当前旧节点对应的新节点的next 指向 当前旧节点的next指向的节点对应的新节点map[cur]->next = map[cur->next];// 当前旧节点对应的新节点的random 指向 当前旧节点的random指向的节点对应的新节点map[cur]->random = map[cur->random];cur = cur->next;}// 返回新链表的头节点return map[head];}
};