003_哈希表 - Leetcode - 编程

# 一、理论基础

哈希法使用的场景通常为需要快速判断一个元素是否出现在集合里，哈希表牺牲空间换取时间。
哈希表通过哈希函数来进行 key 和 value 的映射。

映射时，可能会发生哈希碰撞。（尤其是元素数量大于容器数量的时候）
解决哈希碰撞有拉链法和线性探测法。

C++ 中常见的三种哈希结构：数组（array、vector）、集合（set）、映射（map）。

集合	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
`std::set`	红黑树	有序	否	否	O(log n)	O(log n)
`std::multiset`	红黑树	有序	是	否	O(log n)	O(log n)
`std::unordered_set`	哈希表	无序	否	否	O(1)	O(1)

映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
`std::map`	红黑树	有序	否	否	O(log n)	O(log n)
`std::multimap`	红黑树	有序	是	否	O(log n)	O(log n)
`std::unordered_map`	哈希表	无序	否	否	O(1)	O(1)

要使用集合来解决哈希问题的时候，优先使用 unordered_set ，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用 set ，如果要求不仅有序还要有重复数据的话，那么就用 multiset 。 map 同理。

# 二、题目实践

# 1、242. 有效的字母异位词

#哈希

思路很简单，用 vector 维护一个 “哈希表”，分别遍历 s 和 t，最后再遍历哈希表。

class Solution {
public:
    bool isAnagram(string s, string t) {
        std::vector<int> hashtable(26, 0);
        for(char c : s) { ++hashtable[c-'a']; }
        for(char c : t) { --hashtable[c-'a']; }
        for(auto v : hashtable) {
            if(v != 0) {
                return false;
            }
        } return true;
    }
};

# 2、349. 两个数组的交集

#哈希

这里要注意，题目给了数组中数值的范围在 1000 以内，所以可以用数组来做哈希，不用非得 unordered_set 才能搞定的。
维护一个数组，nums1 和 nums2 轮流遍历以便，做相应的标记即可：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        int hashTable[1001] = {0};
        
        for(int i : nums1) {
            if(hashTable[i]==0) hashTable[i]++;
        }

        for(int i : nums2) {
            if(hashTable[i]==1) hashTable[i]++;
        }

        for(int i = 0; i < 1001; ++i) {
            if(hashTable[i]==2) ret.push_back(i);
        } return ret;
    }
};

这里是使用 unordered_set 的版本，就当作熟悉 set 的操作了：（这里注意，定义 set 时可以直接把 nums1 加载进来）

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        unordered_set<int> Num1Set(nums1.begin(), nums1.end());
        for(int i : nums2) {
            if(Num1Set.find(i) != Num1Set.end()) {
                Num1Set.erase(i);
                ret.push_back(i);
            }
        } return ret;
    }
};

# 3、202. 快乐数

#哈希 #快慢指针

这道题要不是放在哈希系列里面，我是怀疑我能不能想到这题的思路的。
甚至我想到了思路我都不敢确定：为什么无限循环的数字一定是重复出现的，即为什么是成环，而不是无限不循环？

思路 1：
用一个 set 记录出现过的所有情况，如果出现重复，说明遇到环了，则该数一定不是快乐树。否则，如果当数值为 1，说明该数为快乐树。（但是，有没有可能一直不出现重复，但是无限不循环一直不遇到 1 ？）

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> mySet;
        for(int sum = 0; ; n = sum) {
            sum = getSum(n);
            if(sum == 1) { return true; } 
            if(mySet.find(sum) != mySet.end()) {
                return false;
            } else {
                mySet.insert(sum);
            }
        }
    }

    int getSum(int n) {
        int sum = 0;
        while(n > 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        } return sum;
    }
};

思路 2：
这个思路很厉害，如我们刚才所说，如果遇到重复出现的数字，可以看作是成环了。所以可以把求快乐数过程中计算的一连串的数字当作是一个链表，把该问题等效看作是判断一个链表是否成环，利用快慢指针。


class Solution {
public:
    bool isHappy(int n) {
        int slow = n;
        int fast = getNext(n);
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        } return fast==1;
    }

    int getNext(int n) {
        int sum = 0;
        while(n > 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        } return sum;
    }
};

另外一种解法是数学法，就不展开讨论了：

// 根据数学规律，得知只存在一个环，这个环就是4, 16, 37, 58, 89, 145, 42, 20
// 如果n出现在环内，说明不对；否则n最终能转换成1，说明OK
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> cycleNum{4, 16, 37, 58, 89, 145, 42, 20};
        while(n != 1 && cycleNum.find(n) == cycleNum.end()) {
            n = getNext(n);
        } return n==1;
    }

    int getNext(int n) {
        int sum = 0;
        while(n > 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        } return sum;
    }
};

# 4、1. 两数之和

#哈希

又回到了梦开始的地方 😃
已经不知道是第几次做这道题目了。这次我没看清题意，返回的是这两个值，而不是值的下标：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_set<int> seen;
        for(auto v : nums) {
            if(seen.find(target - v) != seen.end()) {
                return {v, target-v};
            } else {
                seen.insert(v);
            }
        } return {};
    }
};

所以这当然是不合题意的。

由于我们同时要记录索引和值，所以要用到 map：
这里我们以数组的值为 key，以索引为 value

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> seen;
        for(int i = 0; i < nums.size(); i++) {
            auto it = seen.find(target-nums[i]);
            if(it != seen.end()) {
                return {i, it->second};
            }
            seen[nums[i]] = i;
        } return {};
    }
};

# 5、454. 四数相加 II

注意审题！！

题目是要返回符合条件的元组的数量！即四个数组下标的一些组合值！
并不是要让我们枚举所有情况，所以这题没有看起来那么难。

把数组两两分组，(a+b) + (c+d) = 0，然后就变成一个两数之和，只不过我们是要计算所有的可能性的次数。

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int cnt = 0;
        unordered_map<int, int> hashmap;  // key:a+b的数值，value:a+b数值出现的次数

        // 两层循环，将 a + b 的所有求和组合可能记录到hashmap中
        for(int a : nums1) {
            for(int b : nums2) {
                hashmap[a + b]++;
            }
        }

        // 两层循环，遍历每一种 c + d 的求和组合可能，如果与 a + b 互补，加上相应的计数
        for(int c : nums3) {
            for(int d : nums4) {
                if(hashmap.find(0 - (c + d)) != hashmap.end()) {
                    cnt += hashmap[0 - (c + d)];
                }
            }
        } return cnt;
    }
};

这里，为什么要两两分组，而不是 3 + 1 分组呢，我的想法是，降低复杂度。
如果是后者，则在构建哈希表时需要先三重循环造表。

# 6、383. 赎金信

#哈希

典型的哈希题，但由于只出现小写字母，可以只用一个数组来实现：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> hash(26, 0);
        for(char c : magazine) {
            ++hash[c - 'a'];
        }

        for(char c : ransomNote) {
            if(hash[c - 'a'] > 0) {
                --hash[c - 'a'];
            } else {
                return false;
            }
        } return true;
    }
};

以前写了一种更简洁但更耗时一丢丢的解法：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int hashtable[26] = {0};
        for(char c : magazine) { hashtable[c-'a']++; }
        for(char c : ransomNote) { hashtable[c-'a']--; }
        for(int i : hashtable) {
            if( i < 0) {
                return false;
            }
        } return true;
    }
};

快慢指针哈希