[LeetCode] 哈希表 I — 242#有效的字母异位词 | 349#两个数组的交集 | 202#快乐数

哈希表

基础知识
常见的哈希结构
数组
- 242# 有效的字母异位词
Set
- 基础语句
- 349# 两个数组的交集
- 202# 快乐数
Map
- 基础语句
- 1# 两数之和

基础知识

哈希表常用于快速判断一个元素是否在集合中，空间换时间

哈希表是根据key（如数组的索引下标）直接进行访问的数据结构

哈希函数：将key映射到哈希表上的索引 index = hashFunction(key) = (hashCode(key) % tableSize) mod tableSize

hashCode()通过特定编码方式把key转化为数值

哈希碰撞：不同的key引射到了相同的下标，解决方法：拉链法 和 线性探测法

拉链法：将发生冲突的元素存储在链表中，不需要tableSize大于dataSize
线性探测法：向下找空位，需要tableSize一定大于dataSize

常见的哈希结构

数组

常用于key的数值十分受限，密度高的情况，相比起set时间和空间复杂度低（set把数值映射到key上要做hash计算）

set（集合）

常用于key较少、分散且数值跨度大的情况（使用数组会造成空间的极大浪费）

一般来说，当要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的；如果需要集合是有序的则用set；如果要求不仅有序还要有重复数据则用multiset

map（映射）

map 是一个key-value 的数据结构

map中对key是有限制，而对value没有限制，因为key的存储方式是用红黑树实现的

hash_set和hash_map与unordered_set和unordered_map的关系：

功能相同，但unordered_set在C++11被引入标准库，因此建议使用unordered_set

数组

常用于key的数值十分受限，密度高的情况，相比起set时间和空间复杂度低（set把数值映射到key上要做hash计算）

242# 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

由于字符串只有小写字母，因此定义一个长度为26的数组record记录字符串中字符出现的次数

// 哈希数组
// O(n) 0ms; O(1) 9.51MB
class Solution {
public:bool isAnagram(string s, string t) {int record[26] = {0};for (int i = 0; i < s.size(); i++) {record[s[i] - 'a']++;}for (int i = 0; i < t.size(); i++) {record[t[i] - 'a']--;}for (int i = 0; i < 26; i++) {if (record[i] != 0) return false;}return true;}
};

空间复杂度：一个常量大小的辅助数组O(26)，即 O(1) 或 O(S)

Set

常用于key较少、分散且数值跨度大的情况（使用数组会造成空间的极大浪费）

基础语句

// 创建
unordered_set<int> hashset;
unordered_set<int> hashset(vector.begin(), vector.end()); // 范围构造函数，参数为两个迭代器，将vector的所有元素插入hashset中，遍历O(n)，插入所有元素到set的时间复杂度为O(n)~O(n^2)（哈希冲突严重）
// 查询
unordered_set.find(key)  // O(1) 如果key存在，返回一个指向该元素的迭代器；不存在返回特殊值unordered_set.end()
// 插入
unordered_set.insert(key)
// 长度
unordered_set.size()
// 桶数量
unordered_set.bucket_count() // unordered_set会动态扩容（rehashing）

349# 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

数组的交集：同时出现在数组中的元素的集合

示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

唯一且无序，选择unordered_set

先将nums1转化为unordered_set，再取unordered_set与nums2的交集

// unordered_set
// O(n+m) 8ms; O(n) 14.43MB
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> nums1_set(nums1.begin(), nums1.end());unordered_set<int> result_set; // 使用set为最终结果去重for (int num : nums2) {if (nums1_set.find(num) != nums1_set.end()) result_set.insert(num);}return vector<int>(result_set.begin(), result_set.end());}
};

由于本题力扣对数组的数值进行了大幅限制，因此也可使用哈希数组

// 哈希数组 & unordered_set
// O(n+m) 4ms; O(n) 14.58MB
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set;int hash[1001] = {0};for (int num : nums1) {hash[num] = 1;}for (int num : nums2) {if (hash[num] == 1) result_set.insert(num);}return vector<int>(result_set.begin(), result_set.end());}
};

202# 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2：
输入：n = 2
输出：false
提示：

1 <= n <= 2^31 - 1

该题的突破点在于无限循环（结果会收敛到1 或无限循环）

无限循环的原因：对于一个非负整数，其每位平方和范围有限（如三位数的每位平方和最大为243）

// unordered_set
// O(logn) 0ms; O(logn) 8.25MB
class Solution {
public:int getSum(int n) {int sum = 0;while (n) {sum += (n % 10) * (n % 10);n /= 10;}return sum;}bool isHappy(int n) {unordered_set<int> hashset;while (n != 1) {if (hashset.find(n) != hashset.end()) return false;hashset.insert(n);n = getSum(n); }return true;}
};

用集合记录可能导致集合过大，递归的层次较深也会导致调用栈崩溃

另一种方法是快慢指针法：

每位平方和的过程是一个隐式链表，则转换为链表中是否有环的问题，fast走两步，slow走一步（相对速度为1），二者相等即存在环

由于该题的特殊性——为1时1自身形成环，因此只需判断fast和slow相遇时（环中）是否为1

// 快慢指针法
// O(logn) 0ms; O(1) 7.6MB
class Solution {
public:int bitSquareSum(int n) {int sum = 0;while (n) {sum += (n % 10) * (n % 10);n /= 10;}return sum;}bool isHappy(int n) {int slow = n, fast = n;do {slow = bitSquareSum(slow);fast = bitSquareSum(bitSquareSum(fast));} while (slow != fast);return slow == 1;}
};

Map

基础语句

// 创建
unordered_map<int, int> hashmap;// 查询
auto iter = unordered_map.find(key); // O(1)，不存在返回 unordered_map.end()
iter->first // 查key
iter->second // 查value
auto iter = M.begin(); // 第一个元素
iter+1 // 下一个元素// 插入
unordered_map[key] = value;
unordered_map.insert(pair<int, int>(key, value));

1# 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

需要查询元素的同时，还需要元素对应的下标，因此用map，key可以无需，因此用unordered_map

{key：数据元素，value：对应下标}

// unordered_map
// O(n) 3ms; O(n) 14.59MB
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hashmap;for (int i = 0; i < nums.size(); i++) {auto iter = hashmap.find(target - nums[i]);if (iter != hashmap.end()) return {iter->second, i};hashmap[nums[i]] = i;// hashmap.insert(pair<int, int>(nums[i], i));}return {};}
};