C++算法训练营 Day6 哈希表（1）

1.有效的字母异位词

• LeetCode：242.有效的字母异位词

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

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:

输入: s = “rat”, t = “car”
输出: false

• 解题思路：

由题可知，字母异位词是两个数组字母相同但是顺序不同，我们需要快速的找出某个值是否在表中，因此考虑使用哈希表。

1.使用一个大小为26的数组（对应26个英文字母）作为计数器；
2.遍历第一个字符串，将出现的字母对应增加相应字符的计数；
3.遍历第二个字符串，将出现的字母减少相应字符的计数；
4.如果两个字符串是字母异位词，最终计数器所有位置都应为0。

其中创建一个包含26个整数的数组（初始化为0），每个位置对应一个字母，如：

res[0] → ‘a’ 的计数
res[1] → ‘b’ 的计数
…
res[25] → ‘z’ 的计数

然后将字符到索引利用一个巧妙的ASCII码进行转换s[i] - 'a'，如：

‘a’ 的ASCII码是97
‘b’ 是98，
…，
‘z’ 是122

然后通过计算可得：

‘a’ - ‘a’ = 0
‘b’ - ‘a’ = 1
…
‘z’ - ‘a’ = 25

从而就得到了每个字母的对应位置。由此便可进行计算

如：
（1）有效字母异位词

s = “anagram”, t = “nagaram”

1.遍历s: a→+1, n→+1, a→+1, g→+1, r→+1, a→+1, m→+1
2.遍历t: n→-1, a→-1, g→-1,a→-1, r→-1, a→-1, m→-1
3.所有计数器归零 → 返回true

（2）无效字母异位词

s = “rat”, t = “car”

1.遍历s: r→+1, a→+1, t→+1
2.遍历t: c→-1, a→-1, r→-1
3.最终计数器中: a:0, r:0, t:+1,c:-1
t,c是非零值 ，因此返回false

class Solution {
public:bool isAnagram(string s, string t) {//步骤1：创建计数器数组int res[26] = {0};//步骤2：遍历字符串s，增加字符计数for(int i = 0; i < s.size(); ++i) res[s[i] - 'a']++;//步骤3：遍历字符串t，减少字符计数for(int i = 0; i < t.size(); ++i) res[t[i] - 'a']--;//步骤4：检查计数器是否全为0for(int i = 0; i < 26; ++i) {if(res[i] != 0) return false;  //任何非零值都表示计数不匹配}return true;  //所有计数均为0，是字母异位词}
};

2.两个数组的交集

• LeetCode：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] 也是可通过的

• 解题思路：

本题要求我们找出两个数组中的相同元素，涉及到快速查找某个元素是否在表中，因此考虑用哈希表来求解，此外若题目限制了数组的大小可以选择数组来解题，但是本道题没有规定数组的大小，因此无法用数组来做哈希表，而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。因此我们考虑使用set或map，对于本题来说，我们只需返回相同的元素即可，且不要求顺序，因此我们使用unordered_set求解。

首先unordered_set中数值要求不能重复，因此会自动过滤重复元素，我们可以创建一个结果集用来存放交集元素，同时将数组nums1转换为哈希表，即：

[1,2,2,1] → {1,2}

具体操作为：

  	unordered_set<int> result_set; //存储结果的集合（自动去重）unordered_set<int> nums_set(nums1.begin(), nums1.end()); //将nums1转换为哈希集合（自动去重）

然后我们遍历nums2，同时在哈希表nums1中寻找nums2中有的元素，若找着了，就把这个元素插入到结果集中即：

for (int num : nums2) {//检查当前元素是否存在于nums1的集合中if (nums_set.find(num) != nums_set.end()) {result_set.insert(num);  //存在则加入结果集}}

对于int num：是声明了一个临时变量num，类型是int，每次循环时，num会被自动赋值为nums2的当前元素。注意：这里是值拷贝，即复制元素值。nums2：则是要遍历的容器，这里是vector。编译器会自动处理迭代过程。即执行流程为：

第一次循环：num = nums2的第一个元素
第二次循环：num = nums2的第二个元素
…
直到遍历完nums2中所有元素

if (nums_set.find(num) != nums_set.end()) 是判断元素num是否存在于集合nums_set中的标准方法。

nums_set.find(num)：在集合中查找键为num的元素

若找到：返回指向该元素的迭代器
若未找到：返回一个特殊的迭代器nums_set.end()（表示集合末尾的下一个位置，为无效位置）

最后将结果集转化为vector返回，即：

  return vector<int>(result_set.begin(), result_set.end());

整体C++代码为：

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {//存储结果的集合（自动去重）unordered_set<int> result_set; //将nums1转换为哈希集合（自动去重）unordered_set<int> nums_set(nums1.begin(), nums1.end());//遍历nums2中的每个元素for (int num : nums2) {//检查当前元素是否存在于nums1的集合中if (nums_set.find(num) != nums_set.end()) {result_set.insert(num);  //存在则加入结果集}}//将结果集合转换为vector返回return vector<int>(result_set.begin(), result_set.end());
}

3.快乐数

• LeetCode：202.快乐数

编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为：

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

示例 1：

示例 2：

-解题思路：

由题意，对于一个正整数，重复将其替换为各位数字的平方和，最终结果变为1的数即为快乐数。而无限循环时不是快乐数，而在无限循环的过程中，一定会出现重复的结果，因此我们需要在结果集中快速寻找是否存在重复的结果，若存在即陷入循环了，就不是循环数。此外对结果的顺序不做要求，因此选择unordered_set。

首先，我们需要计算给定n的各位平方和，即：

 //计算数字各位平方和的辅助函数int getsum(int n) {int sum = 0;while(n) {  //当n不为0时继续处理sum += (n % 10) * (n % 10);  //取最后一位数字并平方n /= 10;  //移除最后一位数字}return sum;}

这是一个基本的处理一个整数各个位的方法，如：

初始：n=19
第一次循环：19 % 10 = 9, 则sum = 81, 19 / 10 = 1，即n更新为1
第二次循环：1 % 10 = 1, sum = 81 + 1 = 82, 1 / 10 = 0
不满足循环条件，返回82

然后，我们需要创建一个结果集，用来存放所有sum。并使用哈希集合检测循环，若结果等于1，则说明为快乐数；若结果重复出现，则说明非快乐数。

  unordered_set<int> res;  // 储出现过的计算结果while(1) {  //无限循环直到找到结果int sum = getsum(n);  //计算当前数字的平方和//检查是否满足快乐数条件if(sum == 1) return true;  //检查是否出现循环（结果重复）if(res.find(sum) != res.end()) return false;else res.insert(sum);  //记录新结果n = sum;  //更新n为新的计算结果，确保每次迭代使用最新计算结果}

整体代码为：

class Solution {
public:int getsum(int n) {int sum = 0;while(n) {  //当n不为0时继续处理sum += (n % 10) * (n % 10);  //取最后一位数字并平方n /= 10;  //移除最后一位数字}return sum;}//判断是否为快乐数bool isHappy(int n) {unordered_set<int> res;  //存储出现过的计算结果while(1) {  // 无限循环直到找到结果int sum = getsum(n);  //计算当前数字的平方和//检查是否满足快乐数条件if(sum == 1) return true;  //检查是否出现循环（结果重复）if(res.find(sum) != res.end()) return false;else res.insert(sum);  //记录新结果n = sum;  //更新n为新的计算结果}}
};

4.两数之和

• LeetCode：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]

• 解题思路

本题不是直接找两个数，而是对于每个元素nums[i]，检查target - nums[i]是否存在于之前遍历过的元素中，其思路与有效字母异位词的思路一致。即如果a + b = target
那么b = target - a。因此我们可以使用哈希表：使用unordered_map存储已遍历元素的值和索引，通过一次遍历，边遍历边检查边存储。

首先建立结果集：

unordered_map<int,int> res//键：元素值，值：元素索引

key用来存储数组元素的值，用于快速查找；value用来存储该元素的索引，用于最终返回结果。

然后通过遍历结果集查找是否存在target - a，若存在返回下标，若不存在返回空。即整体流程为：

假设我们输入：

nums = [2, 7, 11, 15], target = 9

执行流程：

第一次循环：i=0，nums[0]=2
结果集中查找9-2=7（不存在）
插入map: {2:0}
第二次循环： i=1，nums[1]=7
结果集中查找9-7=2（找到，索引为0）
返回[0,1]

for(int i = 0; i < nums.size(); i++) {// 尝试寻找能与nums[i]配对的数auto iter = map.find(target - nums[i]);// 如果找到配对if(iter != map.end()) {return {iter->second, i};  // 返回两个索引}// 将当前元素存入map（先检查后存储，避免自匹配）map.insert(pair<int, int>(nums[i], i)); }
return { };

整体代码为：

vector<int> twoSum(vector<int>& nums, int target) {std::unordered_map<int,int> res;  //键：元素值，值：元素索引for(int i = 0; i < nums.size(); i++) {//尝试寻找能与nums[i]配对的数auto it = res.find(target - nums[i]);//如果找到配对if(it != res.end()) {return {it->second, i};  //返回两个索引}  //将当前元素存入map（先检查后存储，避免自匹配）res.insert(pair<int, int>(nums[i], i)); }return {};  
}

pair<int, int>中pair为是C++标准库中的模板类，用于存储两个值作为一个单元。这里相当于创建了一个临时对象，包含：first = nums[i]和second = i。当插入元素时，必须同时提供key和value，而pair正好把这两个值打包成一个对象。