哈希表核心原理与 C++ 实战应用

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;
    }
};

先对第一个字符串计数加一，再对第二个字符串减一。如果中途出现负数，说明第二个字符串中该字符多了，直接返回 false。

3. 存在重复元素

虽然题目涉及查重，但排序也是一种常见解法。不过在实际开发中，如果需要频繁查询，哈希集合（unordered_set）通常比排序更高效。下面的示例展示了通过排序后相邻比较的方式实现去重检测。

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;  
    }  
};

4. 存在重复元素 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])){
                if(i-hash[nums[i]]<=k) return true;
            }
            hash[nums[i]]=i;
        }
        return false;
    }
};

注意更新 hash 时要覆盖旧索引，因为我们要找的是最近的距离。

5. 字母异位词分组

这是一个典型的'键变换'场景。将字符串排序后作为哈希表的 Key，原始字符串作为 Value 放入列表。这样所有异位词都会归到同一个 Bucket 里。

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;
    }
};

掌握这些模式后，面对类似的查找和分组问题，就能快速构建出高效的解决方案了。