哈希表核心原理与经典算法实战

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        if(n != m) return false;
        int hash[26] = {0};
        for(int i = 0; i < n; i++){
            hash[s1[i] - 'a']++;
        }
        for(int i = 0; i < n; i++){
            hash[s2[i] - 'a']--;
            if(hash[s2[i] - 'a'] < 0) return false;
        }
        return true;
    }
};

存在重复元素

检测数组中是否有重复值。虽然排序法也能解决，但哈希集合的思路更直观——只要插入失败就说明有重复。

不过题目给出的示例代码采用了排序方案，逻辑同样严谨。排序后相邻元素若相等，则必然存在重复。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
};

存在重复元素 II

这次要求重复元素的下标差不能超过 k。这时候不仅要记录是否存在，还要记录位置。

用哈希表存储 数值 -> 下标。每次遇到已存在的数值，就计算当前下标与之前下标的差值，若满足条件直接返回 true。记得更新下标为最新位置。

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])){
                if(i - hash[nums[i]] <= k) return true;
            }
            hash[nums[i]] = i;
        }
        return false;
    }
};

字母异位词分组

将字符串按字母异位词归类。核心在于找到一种'规范键'，让互为异位词的字符串拥有相同的键。

对每个字符串排序后的结果作为 key，原字符串放入 value 列表中。最后收集所有列表即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> hash;
        for(auto& e : strs){
            string ret = e;
            sort(ret.begin(), ret.end());
            hash[ret].push_back(e);
        }
        vector<vector<string>> a;
        for(auto& [x,y] : hash){
            a.push_back(y);
        }
        return a;
    }
};

掌握这些模式，面对涉及查找、计数或分组的问题时，就能快速定位到哈希表的适用场景。