算法（七）--哈希

哈希

解决哈希表问题的精髓就在如何设计键。利用键的唯一性去解决问题。

cpp数据结构

1. unordered_map

std::unordered_map<int, std::string> myMap;

myMap[1] = "One";          // 插入或更新
myMap.insert({2, "Two"});  // 插入
myMap.erase(1);            // 删除
auto it = myMap.find(2);   // 查找键为2的元素

1. unordered_set / 可以做到O(1)的查找某个元素在不在集合中

std::unordered_set<int> mySet;

mySet.insert(10);         // 插入
mySet.erase(10);          // 删除
auto it = mySet.find(10); // 查找元素10

1. unordered_multimap / 可以存储重复的键

std::unordered_multimap<int, std::string> myMultimap;

myMultimap.insert({1, "One"});
myMultimap.insert({1, "Uno"}); // 允许相同的键1

1. unordered_multiset

std::unordered_multiset<int> myMultiset;

myMultiset.insert(10);
myMultiset.insert(10); // 允许重复元素

两数之和

对于每个x，先查找哈希表中是否存在target - x这样的键，如果有，返回{i, hash[target - x]}，否则将x插入哈希表中。

字母异位词

如何判断两个字符串的无序相同性，最好的办法是采用map。map的键是字符串中出现的字符，值是字符出现的次数，判断这两个map是否相同即可判断是否是字母异位词

unordered_map<char, int> map;
for(int i = 0; i < 26; i++) {
    map['a' + i] = 0;
}

字母异位词分组（好题）

本题的难点在于如何确定一个字母异位词的键的形式。这里采用排序的形式，将字母异位词进行排序后储存到哈希表中。同样是先查找，如果没有说明是新的词，插入到哈希表中，值就是该异位词的集合。

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for(string str : strs) {
            string cur = str;
            sort(cur.begin(), cur.end());
            map[cur].push_back(str);
        } 
        vector<vector<string>> ans;
        for(auto pair : map) {
            ans.push_back(pair.second);
        }
        return ans;
    }

最长连续序列

对每个当前数x，去找n次数组中有没有x+1，x+2，x+3，x+4，…；再更新长度最小值. 优化就是利用undered_set的查找时间复杂度O(1)。

    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash(nums.begin(), nums.end());
        int ans = 0;
        for(int num : nums) {
            if(hash.find(num - 1) == hash.end()) {
                int cur = num;
                int len = 1;
                while(hash.find(cur + 1) != hash.end()) {
                    cur++;
                    len++;
                }
                ans = max(ans, len);
            }
        }
        return ans;
    }

同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

思路：用两个哈希表记录s到t和t到s的映射关系，如果出现s到t1和s到t2的映射，说明不成立。

    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> s2t, t2s;
        for(int i = 0; i < s.size(); i++) {
            char a = s[i], b = t[i];

            // 这是判断一对一关系是否成立的经典模式，需要记住
            if(s2t.count(a) > 0 && s2t[a] != b ||
            t2s.count(b) > 0 && t2s[b] != a) {
                return false;
            }

            s2t[a] = b;
            t2s[b] = a;
        }
        return true;
    }

单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

就是在同构字符串的基础上加上了s的单词拆分parse的过程。这里用stringstream来拆分字符串。

    bool wordPattern(string pattern, string s) {
        unordered_map<char, string> p2s;
        unordered_map<string, char> s2p;
        stringstream ss(s);
        string cur;
        for(char c : pattern) {
            if(!(ss >> cur)) return false;
            if(p2s.count(c) > 0 && p2s[c] != cur ||
            s2p.count(cur) > 0 && s2p[cur] != c) {
                return false;
            }
            p2s[c] = cur;
            s2p[cur] = c;
        }
        return !(ss >> cur);
    }

有环检测

用哈希表储存出现过的节点，如果出现过就说明有环。但是空间开销要比双指针的大。

    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> hash;
        while(head) {
            if(hash.count(head) > 0) return true;
            hash.insert(head);
            head = head->next;
        }
        return false;
    }