算法实战：哈希表核心概念与应用

遍历数组 n 次，每次哈希表的插入和查询操作的平均时间复杂度为 O(1)，总时间复杂度降为 O(n)，空间复杂度为 O(n)。

判断是否为字符串重排

优先判断长度——长度不同，一定不是重排。使用数组模拟哈希表统计每一个字母出现的次数，两个字符串每一个字母出现的次数都相同，那么是字符串重排。

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        int hash[26] = {0}; // 下标对应字母，数组值对应出现次数
        for (auto& e : s1) {
            hash[e - 'a']++; // 统计字符串 s1 每个字母出现次数
        }
        for (auto& e : s2) {
            hash[e - 'a']--; // 判断两个字符串字母出现次数是否相等
            if (hash[e - 'a'] < 0) return false;
        }
        return true;
    }
};

存在重复元素Ⅱ

题目要求在数组中查找是否存在两个相同的元素，且它们的下标差小于等于 k。

算法思路： 使用哈希表记录数据和下标，循环判断当前元素是否出现过。如果出现过，检查下标差是否满足条件。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash; // <nums[i], i>
        for (int i = 0; i < nums.size(); i++) {
            int tmp = nums[i];
            if (hash.count(tmp) && abs(i - hash[tmp]) <= k) {
                return true;
            }
            hash[nums[i]] = i; // 哈希表加入当前元素
        }
        return false;
    }
};

字母异位词分组

通俗理解题目要求我们把这些是字母异位词的放在一块。

算法思路： 创建一个 key 为 string（排序后的字符串，方便判断），value 为 vector（排序前的字符串）的哈希表。遍历字符串数组，先对当前字符串进行排序，看哈希表中是否存在，存在就在对应 value 进行存储，不在就插入新的 key。最后返回每一个 value 即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for (auto& e : strs) {
            string tmp = e;
            sort(tmp.begin(), tmp.end());
            if (hash.count(tmp)) {
                hash[tmp].push_back(e); // 对应数组添加当前字符串
            } else {
                hash[tmp] = {e}; // 添加当前排序字符串
            }
        }
        vector<vector<string>> ret;
        for (auto& [x, y] : hash) {
            ret.push_back(y);
        }
        return ret;
    }
};

这道题目是哈希表和排序的组合，如果知道思路的话，相信也是不在话下了。

总结

哈希表的核心优势在于以空间换时间，实现高效操作，一定程度上时间复杂度优化，处理动态数据更灵活。学会灵活使用哈希表这个强有力的工具，能让算法解题事半功倍。