目录

前言

一、哈希表基础

242.有效的字母异位词

49.字母异位词分组

438.找到字符串中所有字母异位词

二、set实现的哈希表

349. 两个数组的交集

三、map实现的哈希表

350.两个数组的交集 II

1. 两数之和

454.四数相加II

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树；

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。

因此要使用集合来解决哈希问题的时候，优先使用unordered_set，它的查询和增删效率最优（O(1)）；如果需要集合是有序的，用set，如果要求不仅有序还要有重复数据的话，用multiset。红黑树查询和增删效率为（O(logn)）。

一、哈希表基础

242.有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map charNum;
        for (int i = 0; i < s.size(); i++){
            charNum[s[i]]++;
        }
        for (int i = 0; i < t.size(); i++) {
            charNum[t[i]]--;
        }
        for (unordered_map::iterator it = charNum.begin(); it != charNum.end(); it++) {
            if (it->second != 0) return false;
        }
        return true;
    }
};

鉴于元素都是小写字母，也可以定义一个长度为26的数组，存放内容为字母的ASCII码。

类似题目：383.赎金信。较为简单，此处不再贴出。

49.字母异位词分组

vector> groupAnagrams(vector& strs) {       
        unordered_map> resMap;
        for (int i = 0; i < strs.size(); i++) {
            int counts[26] = { 0 };
            for (int j = 0; j < strs[i].size(); j++) {
                counts[strs[i][j] - 'a']++;
            }
            string countsStr;
            for (int k = 0; k < 26; k++) {
                countsStr.append(to_string('a' + k));
                countsStr.append(to_string(counts[k]));
            }
            resMap[countsStr].push_back(strs[i]);
        }
        vector> res;
        for (unordered_map>::const_iterator it = resMap.begin(); it != resMap.end(); it++) {
            res.push_back(it->second);
        }
        return res;
    }

本题可以选择unordered_map的键值为字符串，该字符串内容为字母+出现的次数。采用该方式，时间复杂度为O(n+k)，其中k为最长字符串的长度。

另一种方式是对每个str利用sort进行排序后，作为unordered_map的键值。由于sort的时间复杂度为O(logk)，从而这一方法的时间复杂度为O(nlogk)。

438.找到字符串中所有字母异位词

vector findAnagrams(string s, string p) {
        vector res;
        unordered_map charT;
        for (int i = 0; i < p.size(); i++) {
            charT[p[i]]++;
        }
        //储存目标字符串待比较信息
        unordered_map charTemp = charT;
        int count = p.size();
        int slow = 0;
        int fast = 0;
        while (fast < s.size()) {          
            //快指针比慢指针提前移动字符p的长度
            if (fast < p.size()) {           
                if (charT[s[fast]] > 0) {
                    if (charTemp[s[fast]] > 0)   count--;
                    charTemp[s[fast]]--;
                }
            }
            //同时前移快指针和慢指针
            else {
                if (charT[s[slow]] > 0) {
                    if(charTemp[s[slow]] >= 0)  count++;
                    charTemp[s[slow]]++;
                }
                slow++;  
                if (charT[s[fast]] > 0) {
                    if(charTemp[s[fast]] > 0)   count--;
                    charTemp[s[fast]]--; 
                }
            }
            if (count == 0) {
                res.push_back(slow);
            }
            fast++;
        }
        return res;
    }

本题采用了滑动窗口法，类似于数组篇的查找最小子串。采用count标记是否满足要求，两个指针间隔长度为字符串p的长度。滑动窗口法的关键是判断什么时候移动快慢指针，且相应地要进行什么操作。

上述比较小写字母的问题，其实都可以用int count[26]的数组来作为哈希表，进行条件的判断。

---

二、set实现的哈希表

349. 两个数组的交集

vector intersection(vector& nums1, vector& nums2) {
        unordered_set nums(nums1.begin(),nums1.end());
        unordered_set resSet;
        for (int i : nums2) {
            if (nums.find(i) != nums.end()) {
                resSet.insert(i);
            }
        }
        return vector(resSet.begin(),resSet.end());
    }

利用unordered_set，底层实现是哈希表而非红黑树，读写效率最高。本题不使用数组是原因是，待分类元素的数量不确定。

注意基于范围的遍历方式：for(auto i:nums)；以及vector的初始拷贝赋值方式。

---

三、map实现的哈希表

350.两个数组的交集 II

vector intersect(vector& nums1, vector& nums2) {
        vector res;
        unordered_map nums;
        for (auto i : nums1) {
            nums[i]++;
        }
        for (auto j : nums2) {
            if (nums[j] > 0) {
                res.push_back(j);
                nums[j]--;
            }
        }
        return res;
    }

与349类似，只是需要判断该元素是否已输出完毕（取两数组中数量最小者）。

1. 两数之和

vector twoSum(vector& nums, int target) {
        unordered_map numsMap;
        vector res;
        //只需要循环一次，没找到时在unorder_map中插入
        for (int i = 0; i < nums.size(); i++) {
            auto it = numsMap.find(target - nums[i]);
            //找到时一定是数值对的第二个数
            if (it != numsMap.end()) {
                res.push_back(it->second);
                res.push_back(i);
                return res;
            }
            numsMap.insert(make_pair(nums[i], i));
        }
        //没找到返回空
        return {};
    }

本题技巧性很强，利用unordered_map实现的哈希表，只需要一次循环就能完成。一遍查找一边添加数据，返回时利用哈希表查找到的一定是数值对的第一个数据，结合当前下标一起返回即可。

没找到时返回空的语句一定要写，否则会报错。

454.四数相加II

int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
        unordered_map sumMap;
        int res = 0;
        //存放A、B数组元素之和及出现的次数
        for (auto i : nums1) {
            for (auto j : nums2) {
                sumMap[i + j]++;
            }
        }
        for (auto k : nums3) {
            for (auto l : nums4) {
                auto it = sumMap.find(-(k + l));
                if (it != sumMap.end()) {
                    res += it->second;
                }
            }
        }
        return res;
    }

不知道本题有没有比O(n^2)更好的算法，不过这个O(n^2)的算法也比较有技巧性。

其中分组的思想要多加熟悉。遍历A、B数组并将元素之和以及出现的次数记录下来，再遍历C、D数组，查找unordered_map中对应的负值元素出现次数。

---

总结

• 哈希表大小固定时，采用数组作为哈希表。例如小写字母的映射；
• 哈希值比较少、特别分散、跨度非常大，数组大小不确定时，采用set作为哈希表。例如求数组的交集。不需要对数据进行排序，且还不要让数据重复时采用unordered_set，底层实现为哈希而非红黑树，查找效率最高；
• 需要记录键值和数值时，采用map作为哈希表。类型选用思路与上述set一致。