算法 --- hash-程序员充电站

哈希表简介

什么是 hash 表？hash表就是存储数据的容器
作用：快速查找某个元素
什么时候使用hash表？频繁查找某个数时，可以使用 hash 表
如何使用hash表？1.使用hash表容器；2.使用数组模拟简易hash表
什么时候使用数组模拟hash表？<1>. 字符串中的字符；<2>. 数据范围小

算法题目

题目1：1. 两数之和 - 力扣（LeetCode）

题目分析

给定一个整数数组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
只会存在一个有效答案

算法原理

解法1：暴力枚举

第一种遍历的方式：先固定其中一个数，依次与后面的数相加，是否等于 target

第二种遍历的方式：先固定其中一个数，依次与前面的一个数相加，是否等于 target

代码实现

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0; i < nums.size(); i++) { for(int j = 0; j < i; j++) { if(nums[i] + nums[j] == target) { return {j, i}; } } } return { }; } };

解法2：使用 hash 表

为什么暴力解法这么慢呢？因为固定一个数之后需要在前面找一个等于 target – x 的数，如固定7，就需要在前面找到一个等于 target-x=9-7=2 的数。从前向后找太慢了，查找一个数可以使用hash 表。将固定的数的前面的数加入到 hash 表中，固定的数改变之前将该数加入到 hash 表中。hash 表需要结合第二种遍历的方法一起使用。

为什么使用第一种遍历方法，hash 表就不管用了呢？使用第二种遍历方法需要先将所有的元素加入到 hash 表中，之后固定一个数的时候，再去 hash 表中找 target – x 的数。但是如果 nums 中存在元素2，而 target = 4呢？将所有的元素加入到 hash 表中，当固定的数为2时，在 hash 表中找为2的数，能否被找到，可以，但是满足题目要求吗（不能使用两次同一个下标的元素）？不满足。因此对于这样的情况需要判断一些边界情况，太麻烦了。

代码实现

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { // 创建一个hash表 存的是元素和对应元素的下标 unordered_map<int, int>hash(nums.size()); // 遍历nums数组 for(int i = 0; i < nums.size(); i++) { int val = target - nums[i]; // 如果存在 target-nums[i],则直接返回 if(hash.count(val)) { return {hash[val], i}; } // 如果不存在，加入hash表 hash[nums[i]] = i; } return {}; } };

题目2：面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）

题目分析

给定两个由小写字母组成的字符串s1和s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

题目示例

示例 1：

输入:s1 = "abc", s2 = "bca"输出:true

示例 2：

输入:s1 = "abc", s2 = "bad"输出:false

算法原理

如果一个字符串是另一个字符串重排列后的结果，它们会有一个相同的特点：字母出现的次数都相等。因此只需要统计字符串 s1 中每个字母出现的次数，s2 中每个字母出现的次数，在比较对应字母出现的次数是否相等。统计每个字母出现的次数，使用hash表。可以使用数组模拟实现 hash 表，为什么可以？因为题目说了字符串全是小写字母构成，数据范围小。

创建两个 hash 表，遍历两个字符串，分别将字符加入 hash 表，最后比较两个hash表是否相等。当然还可以在此基础进行优化，只使用一个 hash 表，遍历一个字符串，将该字符串中的字母加入到 hash 表中，其次遍历另一个字符串，将遍历到的字符在 hash 表中减去，如果最终 hash 表中的元素个数为0，说明满足题目要求。如果某个字符出现的次数为负数，那么要么这个字符是多余的，要么是 hash 表中没有的，也说明了不满足题目要求。

其次可以做一些小优化：如果一个字符串是另一个字符串重排列后的结果，那么这两个字符串的长度一定相等，若两个字符串的长度不相等，那么根本就不需要进行下一步操作。

代码实现

class Solution { public: bool CheckPermutation(string s1, string s2) { if(s1.length() != s2.length()) { return false; } // 使用数组模拟hash表 int hash[26] = { 0 }; // 加入hash表 for(auto ch : s1) { hash[ch - 'a']++; } for(auto ch : s2) { hash[ch - 'a']--; // 如果出现负数，直接返回false if(hash[ch - 'a'] < 0) { return false; } } return true; } };

题目3：217. 存在重复元素 - 力扣（LeetCode）

题目分析

给你一个整数数组nums。如果任一值在数组中出现至少两次，返回true；如果数组中每个元素互不相同，返回false。

题目示例

示例 1：
输入：nums = [1,2,3,1]
输出：true
解释：
元素 1 在下标 0 和 3 出现。
示例 2：
输入：nums = [1,2,3,4]
输出：false
解释：
所有元素都不同。
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

算法原理

使用《两数之和》题目的思想：固定一个数，在这个数的前面找是否出现相同的元素。

解法：hash 表

class Solution { public: bool containsDuplicate(vector<int>& nums) { // 创建hash表,由于不需要存下标，因此使用set unordered_set<int> hash; // 遍历nums数组 for(int i = 0; i < nums.size(); i++) { // 如果hash表中存在nums[i]，直接返回true if(hash.count(nums[i])) { return true; } // 如果hash表中不存在nums[i]，加入hash表 hash.insert(nums[i]); } // 出循环了，说明不存在重复的元素，返回false return false; } };

题目4：219. 存在重复元素 II - 力扣（LeetCode）

题目分析

给你一个整数数组nums和一个整数k，判断数组中是否存在两个不同的索引i和j，满足nums[i] == nums[j]且abs(i - j) <= k。如果存在，返回true；否则，返回false。

题目示例

示例 1：

输入：nums = [1,2,3,1], k= 3输出：true

示例 2：

输入：nums = [1,0,1,1], k=1输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k=2输出：false

算法原理

这道题与《存在重复元素I》解法相似，只不过在判断是否存在重复元素时，需要判断两个重复元素的下标之差是否小于等于k。因此创建的 hash 表中需要存两个元素，元素和元素对应的下标。

固定一个数，看该数前面是否存在相同的元素，如果存在，还需比较这两个相同的数的下标查是否等于 k，如果小于相等，返回 true。如果不相等，加入 hash 表中，这样会将相同的元素给覆盖掉，如此还能找到最终结果吗？当然可以！！

代码实现

class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { // 创建hash表 unordered_map<int, int> hash; // 遍历nums数组 for(int i = 0; i < nums.size(); i++) { int val = nums[i]; // 如果hash表中存在等于val的元素，且对应元素的下标相减小于等于k，直接返回true if(hash.count(val) && i - hash[val] <= k) { return true;} // 如果hash表中不存在等于val的元素，或者对应元素的下标相减不小于等于k，加入到hash表中 hash[val] = i; } return false; } };

题目5：49. 字母异位词分组 - 力扣（LeetCode）

题目分析

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

题目示例

示例 1:
输入:strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:[["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
在 strs 中没有字符串可以通过重新排列来形成"bat"。
字符串"nat"和"tan"是字母异位词，因为它们可以重新排列以形成彼此。
字符串"ate"，"eat"和"tea"是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:
输入:strs = [""]
输出:[[""]]
示例 3:
输入:strs = ["a"]
输出:[["a"]]

提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i]仅包含小写字母

算法原理

解法：hash表

首先需要判断两个字符是否是字母异位词，如果使用 hash 表来统计两个字符串的字母出现的次数是否相等，会有点麻烦。可以使用排序，两个字符串排序之后如果相等，那么这两个字符串就是字母异位词。接下来考虑如何分组？如何将字母异位词分成一组？这就体现出泛型编程的强大之处了，hash的参数类型为 string和 vector<string>。

最终遍历一遍 hash 表，将 hash 表中的 value 值提取出来。

代码实现

class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { // 创建一个hash表 unordered_map<string, vector<string>> hash; // 根据字符串排好序的结果进行分组 for(string& str : strs) { // 将字符串排好序,不要对str操作 string tmp = str; sort(tmp.begin(), tmp.end()); // 若排序后字符串相等,则进入同一个字符串数组 // hash[tmp]的类型是vector<string>,可以调用push_back函数 hash[tmp].push_back(str); } // 返回值 vector<vector<string>> ret; // 遍历hash表 for(auto& [k, v] : hash) { ret.push_back(v); } return ret; } };