代码随想录之哈希表刷题总结

1.哈希表理论基础

哈希表-（hash table），数组其实就是一张哈希表，哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。如下图：

1.1哈希函数

把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

 若hashCode得到的数值大于哈希表的大小，也就是大于tableSize，为了保证映射出来的索引数值都落在哈希表上面，此时会对数值做一个取模的操作，这样就可以保证学生姓名一定可以映射到哈希表上了。

1.2哈希碰撞

引起原因：学生数量大于哈希表的大小，也就是有几位学生的名字同时映射到哈希表同一个索引下标的位置。

 解决方法：拉链法和线性探测法

1.2.1拉链法

上图在索引1发生了冲突，发生冲突的元素都被存储在链表中，这样就可以通过索引找到

数据规模是dataSize， 哈希表的大小为tableSize

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

1.2.2线性探测法

使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：

1.3常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

- 数组
- set （集合）
- map(映射)

这里数组就没啥可说的了，我们来看一下set。

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

 std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

 std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

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

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

 总结：

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

若在面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法

2.有效的字母异位词

题目描述：

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

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

**说明:** 你可以假设字符串只包含小写字母

思路：

1.定义数组，大小为26，并且初始化为0；

2.遍历字符串s的时候，将s[i]-'a'所在元素做+1操作即可，求相对数值

3.遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值做-1的操作

4.最后检查的时候，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false

注意：

注意第2步的操作不要搞错。

代码：

class Solution {
public:
	bool isAnagram(string s, string t) {
		int arr[26] = {0};
		for (int i = 0; i < s.size(); i++) {
			//不需要记住字符a的ASCII，只要求出一个相对数值就可以
			//arr[s[i]]++;错误写法
			arr[s[i] - 'a']++;
		}
		for (int j = 0; j < t.size(); j++) {
			//arr[t[j]]--;错误写法
			arr[t[j] - 'a']--;
		}
		for (int k = 0; k < 26; k++) {
			if (arr[k] != 0) {
				return false;
			}
		}
		return true;
	}
};

3.两个数组的交集

题目：

 思路：

1.根据题目描述：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序，得到此时可以采用unordered_set

2.如下图：

 注意:

最后的结果要转化为vector<int>的形式

 代码：

class Solution {
public:
	vector<int>twoarrayjiao(vector<int>nums1, vector<int>nums2) {
		unordered_set<int> set(nums1.begin(), nums1.end());
		unordered_set<int> result;
		for (int i = 0; i < nums2.size(); i++) {
			if (set.find(nums2[i]) != set.end()) {
				result.insert(nums2[i]);
			}
		}
		return vector<int>(result.begin(),result.end());

	}
};

4.快乐数

题目：

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

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

如果 n 是快乐数就返回 True ；不是，则返回 False 。

**示例：**

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

思路：

1.首先是计算方式，先定义一个专门统计sum的函数,对于sum的计算步骤要知道

2.考虑到无限循环的情况，要对这一步进行处理，也就是用unordered_set寻找是否有重复出现的情况

3.判断sum的各种情况，为1返回true，不正确的话返回false

注意：

进行判断的时候，是在一个循环内进行判断，直到满足特定的条件

代码：

class Solution {
public:
	int Sum(int n) {
		int sum = 0;
		while (n) {
			sum+= (n % 10) * (n % 10);
			n /= 10;
		}
		return sum;
	}

	bool isHappy(int n) {
		unordered_set<int>set;
		//循环内执行哦
		//下面为错误写法
		/*int sum = Sum(n);
		if (sum == 1) return true;
		if (set.find(sum) != set.end()) {
			return false;
		}
		else {
			set.insert(sum);
		}
		n = sum;*/
		while (1) {
			int sum = Sum(n);
			if (sum == 1) return true;
			if (set.find(sum) != set.end()) {
				return false;
			}
			else {
				set.insert(sum);
			}
			n = sum;
		}
		
	}
};

5.两数之和

题目：

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

**示例:**

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路：

1.查询一个元素是否出现过，或者一个元素是否在集合的时候，就要首先想到哈希法。

2.题目中要求记录元素和对应的下标，并且元素没有要求有序，且不能使用第二遍，因此要使用unordered_map.

3.遍历数组，对于不符合条件的，先将数组中的元素和下标存入定义的unordred_map中

注意：

要知道定义的哈希表中存储的是什么元素和下标，此处是数组中的元素和对应的下标

代码：

class Solution {
	vector<int> twosum(vector<int>nums, int target) {
		unordered_map<int, int> result;
		for (int i = 0; i < nums.size(); i++) {
			auto iter = result.find(target-nums[i]);
			if (iter != result.end()) {
				return { iter->second,i };
			}
			//错误写法，应该是存储访问过的元素和下标
			/*else {
				result[target - nums[i]]++;
			}*/
			else {
				result.insert(pair<int, int>(nums[i], i));
			}
		}
		return {};
	}
};

6.四数相加

题目：

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

**例如:**

输入:

- A = [ 1, 2]
- B = [-2,-1]
- C = [-1, 2]
- D = [ 0, 2]

输出:

2

**解释:**

两个元组如下:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

思路：

1. 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
3. 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
4. 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
5. 最后返回统计值 count 就可以了。

注意：

如何知道次数？
哈希表映射搞懂，数值为两数之和，下标为和的次数。

代码：

class Solution {
public:
	int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
		unordered_map<int,int> maap;
		int count = 0;
		for (int i = 0; i < nums1.size(); i++) {
			for (int j = 0; j < nums2.size(); j++) {
				maap[nums1[i] + nums2[j]]++;
			}
		}
		for (int x : nums3) {
			for (int y : nums4) {
				auto iter = maap.find(0 - (x + y));
				if (iter != maap.end()) {
					count += (iter->second);
				}
			}
		}
		return count;
	}
};

7.赎金信

题目：

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

思路：

1.与有效的字母异位词有异曲同工之效

2.直接数组，容量大小为26，并且其中元素初始化为0，

3.利用数组记录，ransom中各个字符出现的次数，此处计算相对值即可

注意：

没啥注意的

代码：

class Solution {
public:
	bool canConstruct(string ransomNote, string magazine) {
		int arr[26] = { 0 };
		for (int i = 0; i < ransomNote.size(); i++) {
			arr[ransomNote[i]-'a']++;
		}
		for (int j = 0; j < magazine.size(); j++) {
			arr[magazine[j] - 'a']--;
		}
		for (int k = 0; k < 26; k++) {
			if (arr[k] > 0) {
				return false;
			}
		}
		return true;
	}
};

8.三数之和

题目：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

**注意：** 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

思路：

1.使用双指针法，同时遍历nums[i],left（第一个指针）在开头，也就是nums[i]的后面，right(第二个指针)在末尾。

2.根据nums[i]+nums[left]+nums[right]的值与0的大小关系比较，确定具体的操作。

3.记得去重，要包含原始条件，不然会出错。

注意：

刚开始的时候要对数组进行从小到大的排序，不然后续会出错

循环条件要确定明确

代码：

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		vector<vector<int>> result;
		sort(nums.begin(), nums.end());
		for (int i = 0; i < nums.size(); i++) {
			if (nums[0] > 0) return result;
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			int left = i + 1;
			int right = nums.size() - 1;
			while (left < right) {
				if (nums[i] + nums[left] + nums[right] < 0)left++;
				else if (nums[i] + nums[left] + nums[right] > 0) right--;
				else {
					result.push_back(vector<int>{nums[i], nums[left], nums[right] });
					while (left < right && nums[right] == nums[right - 1]) right--;
					while (left < right && nums[left] == nums[left + 1])left++;
					left++;
					right--;
				}
			}
		}
		return result;
	}
};

9.四数之和

题目：

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1,  0, 0, 1], [-2, -1, 1, 2], [-2,  0, 0, 2] ]

思路：

1.其实就是在三数之和的基础上面加一个数

2.先计算两个数组元素的和，每一个都要做剪枝处理(也就是跳过不必要的计算步骤)，同时还要进行去重处理。

3，然后按照三数之和的操作，对left和right进行操作，此时要知道left一定是紧跟着第二个计算的元素，也就是left = j+1,不要写为i+2的形式

注意：

注意剪枝处理的操作，以及去重的操作，此处特殊的是，第二个数组元素也要进行相应的剪枝和去重操作。

代码：

class Solution {
	vector<vector<int>> fournum(vector<int>& nums, int target) {
		vector<vector<int>> result;
		sort(nums.begin(), nums.end());
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] > target && nums[i] >= 0) {
				break;
			}
			else if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			for (int j = i+1; j < nums.size(); j++) {
				if (nums[i] + nums[j] > target && nums[i] + nums[j] > 0) {
					break;
				}
				else if (j > i + 1 && nums[j] == nums[j - 1]) {
					continue;
				}
				int left = j + 1;
				int right = nums.size() - 1;
				while (left < right) {
					if ((long)nums[i] + nums[j] + nums[left] + nums[right] < target) left++;
					else if ((long)nums[i] + nums[j] + nums[left] + nums[right] > target) right--;
					else {
						result.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
						while (left < right && nums[left] == nums[left + 1]) left++;
						while (left < right && nums[right] == nums[right - 1]) right--;
						left++;
						right--;
					}
				}
			}
			
		}
		return result;
	}
};