代码随想录算法训练营第六天| 哈希表理论基础、242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

哈希表理论基础

文档讲解：哈希表理论基础
视频讲解：
目标：了解哈希表的内部实现原理，哈希函数，哈希碰撞，常见哈希表的区别，数组，set 和 map
状态：
场景：> 当我们遇到了需要快速判断一个元素是否出现集合里的时候，就需要考虑哈希法

哈希表要点

哈希表，Hash Table，散列表，指的都是同一个东西，在本文中，我们采用哈希表的叫法。

哈希表是根据关键码的值而直接进行访问的数据结构，学过python的可能知道字典dict这个数据结构，其中的键值对的逻辑和哈希表就很相似。

关键码就是一个元素的索引，就像在数组中，我们可以直接通过下标来对数组中的元素进行访问，因此下标即 0, 1, ..., n就是其关键码。

哈希表能解决什么问题？

一般哈希表可以快速判断一个元素是否出现集合里。

假如我们需要在数据库中查询一个名字，遍历即枚举的时间复杂度是O(n)，而使用哈希表的话只需要O(1)就能做到。

哈希函数

我们一般会使用哈希函数，将数据直接映射为哈希表上的索引，然后就可以通过查询索引快速知道表中是否含有某个元素。

通过hashCode可以把元素值转化为数字，一般hashCode是通过特定编码方式，可以将其他数据格式转化为不同的数值。

一般来说哈希表的大小是有限的，如果元素在经过hashCode转化后，超出了表的范围，那么我们会对其进行一个取模操作，使其映射到表上。

哈希碰撞

正如上面所说，由于哈希表的大小是有限的，因此可能会有元素在取模之后映射到了相同的位置，这就是所谓的哈希碰撞。

一般来说，我们有两种解决方法：拉链法和线性探测法。

拉链法

采用链表的形式，哈希表的每个位置存储一个链表的头节点，将映射到同一位置的元素加入到其对应的链表中，当想要寻找目标元素时，首先定位到该元素所处的链表，然后需要遍历链表才能找出目标元素。

因此，选择合适的哈希表大小，以避免链表过长造成时空上的浪费。

线性探测法

线性探测法要求表的大小即容量需要大于元素的个数，这样当元素位置产生冲突时，后一个映射的元素会顺延值前一个元素的后面位置，如果后面位置也被占据，会接着向后移动，直到找到一个空位来存放。

因此tablesize需要大于datasize，否则没有足够位置存放所有元素。

C++相关

使用哈希法时，一般会采用数组，set（集合），map（映射），这三种数据结构。

下面会给出c++中常用的一些数据结构：

set

set，multiset，unordered_set

map

map，multimap，unordered_map

2024/2/26
以上提到的数据结构后续会逐渐补充详细内容🤗

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

map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

242.有效的字母异位词

题目链接：242.有效的字母异位词
文档讲解：242.有效的字母异位词
视频讲解：学透哈希表，数组使用有技巧！Leetcode：242.有效的字母异位词
目标：
状态：暴力法没想明白，哈希法一点就通🤗

学习前的想法

题目给定了两个字符串，我们需要判断则两个字符串是否包含相同的字母，即每个字符出现的次数相同，但字符序号可能不同。

考虑到set和unordered_set中不能包含重复元素，在上面的学习中，我们可以直到如果集合中有重复数据，选用multiset。

但是看到这道题目并不知道如何去使用，应该还是题目写的比较少。

学习后的想法

暴力的解法是使用两层for循环，同时需要记录字符是否重复出现。

2024/2/26
我是没想到怎么用暴力法实现，后续思考一下

数组是一个简单的哈希表，当需要进行哈希的值较小时，数组是最优的选择。

我们声明一个大小为26的数组，因为一共只有26个字母，这样的话我们遍历一个字符串，当某个字母出现时，就让其在数组对应位置的值加1，这样我们就可以获得这个字符串中每个字母出现的频率。

使用同一个数组，遍历需要进行比较的字符串，当出现某个字母时，将数组中对应位置数值减1。

遍历数组，如果数组中的值全为0，则两字符串所含字母出现次数均相同，反之，不同。

实现

1
2
3
4
5
6
int record[26] = {0};

for(int i = 0; i < s.size(); i++) record[s[i] - 'a']++;
for(int j = 0; j < t.size(); j++) record[t[i] - 'a']--;
for(int k = 0; k < 26; k++) if(record[k] != 0) return false
return true; // record数组所有元素都为零0，说明字符串s和t是字母异位词

349. 两个数组的交集

题目链接：349. 两个数组的交集
文档讲解：349. 两个数组的交集
视频讲解：学透哈希表，set使用有技巧！Leetcode：349. 两个数组的交集
目标：
状态：思路和逻辑还好，c++的stl语法不熟悉

学习前的想法

题目给定两个数组nums1和nums2，需要法案会它们的交集，保证结果中元素唯一，不需要考虑输出顺序。

根据哈希表理论基础中提到的，元素唯一，想到set和unordered_set，可以不考虑吧顺序，则选用unordered_set。

我初步的想法是，两层for循环，第一层遍历nums1，第二层遍历nums2，如果有相同元素，则将该元素置入哈希表即unordered_set中。

尝试写出代码如下：

1
好吧，由于不熟悉c++的stl，思路尽管有，但是写不出代码

2024/2/26
真得去过一遍c++语法了🥲

学习后的想法

思考什么时候用数组、set、map？

使用set实现

整体思路：将nums1转换为set，遍历nums2查询set中是否出现某个元素，如果出现，存入result中。

关于如何转化的问题：（还是要熟悉语法）
unordered_set<int> nums_set(nums1.begin(), nums1.end());

查询时unordered_set效率最高，本题实际上采用了unordered_set。

2024/2/26
采用的数据结构想对了，遍历的逻辑想复杂了

使用数组实现

定义一个1005的数组，处理逻辑和用set相似。

将数组中出现过的元素位置置1，然后遍历另一个数组，比较是否出现即可。

实现

set实现

1
2
3
4
5
6
7
8
9
unordered_set result;
unordered_set num_set(nums1);
for(int i = 0; i < nums2.size(); i++) {
	if(nums_set.find(nums2[i] != nums_set.end()) {
		result.insert(nums2[i]);
	}
}

return vector(result.begin(), result.end());

数组实现

1
2
3
4
5
6
int hash[1005];
unordered_set result;
for(int i = 0; i < nums1.size(); i++) hash[nums1[i]] = 1;
for(int j = 0; i < nums2.size()l j++)
	if(hash[nums2[j]]) result.insert(nums2[j]);
return vector(result.begin(), result.end());

202. 快乐数

题目链接：第202题. 快乐数
文档讲解：第202题. 快乐数
视频讲解：
目标：
状态：

学习前的想法

将一个正整数每一次替换为其各位上数字的平方和，如果这个数最终变为1，则其为快乐数，否则不快乐。🤪

提示使用set解决，但是没有任何思路。

学习后的想法

题目原话：然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。

感觉这一题确实很考验思维能力，抓住题目中无限循环这四个字，如果sum重复出现，说明不是快乐数，否则一直找到sum = 1为止。

因此，我们使用unordered_set来判断sum是否重复出现。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 函数用于获得各位平方和
int getSum(n) {
	int sum = 0;
	while(n) {
		sum += (n % 10) * (n % 10);
		n /= 10;
	}
	return sum;
}
// 函数用于判断是否为快乐数
bool isHappy(int n) {
	unordered_set<int> set;
	while(1) {
		int sum = getSum(n);
		if(sum == 1) return true;
		if(set.find(sum) != set.end()) return false;
		else set.insert(sum);
	}
	n = sum;
}

1. 两数之和

题目链接：1. 两数之和
文档讲解：1. 两数之和
视频讲解：梦开始的地方，Leetcode：1.两数之和，学透哈希表，map使用有技巧！
目标：用map解决哈希问题
状态：

学习前的想法

暴力法，双层for循环遍历。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++) {
	        for(int j = i + 1; j < nums.size(); j++) {
		        if(nums[i] + nums[j] == target) return {i, j};
	        }
        }

        return {};
    }
};

学习后的想法

假设一个场景，我们需要的target值是9，我们现在选中了一个值为6的元素，那么我们是不是还需要一个值为3的元素，这个场景是不是似曾相识？

对，这就是使用hash表来查找元素的场景！

由于我们需要同时存储值和其对应的下标，因此我们在这一题中选用了map来存放数据，即key-value，又我们是通过元素值来查找其下标，所以key为元素的值，value为元素的下标。

map同样也有，multimap，unordered_map，其中unordered_map查找效率最高，因此我们选用它。

实现

1
2
3
4
5
6
7
8
9
// 存放我们遍历过的元素
unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++) {
	// 在map里查询
	if(map.find(target = nums[i]) != map.end())
    	return {map.find(target = nums[i]).value, i};
    map.insert(nums[i], i);
}
return null；

收获与学习时长

学习时长： 3h 00min

收获

学习了数组、set、map实现哈希法方法。