哈希表原理与五大经典算法实战

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

3. 存在重复元素

检测数组中是否有重复元素。虽然哈希集合可以直接解决，但排序后相邻比较也是一种高效的替代方案。

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

检测是否存在两个相同元素且距离不超过 k。需要记录元素上次出现的位置，计算当前索引差。

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

5. 字母异位词分组

将变位词归为一组。将字符串排序后的结果作为 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;
    }
};

掌握这些模式，能显著提升解题效率。实际应用中需根据数据规模和特性选择合适的容器。