如何申请微信企业号_泰安房产网二手房出售_电脑版百度_百度竞价广告怎么收费

---

前言

什么是哈希表？哈希表在算法中具体又有何应用？

哈希表的定义与原理
定义：哈希表是根据关键码值（Key value）而直接进行访问的数据结构。它通过一个哈希函数将键值映射到一个固定大小的数组中，这个数组被称为哈希表。
原理：哈希函数接受一个键值作为输入，并返回一个在哈希表范围内的索引值。理想情况下，不同的键值应该通过哈希函数映射到不同的索引位置，但由于哈希表的大小是有限的，而可能的键值数量是无限的，所以会出现不同的键值映射到同一个索引位置的情况，这被称为冲突。为了解决冲突，有多种方法，如链地址法、开放寻址法等。
哈希表在算法中的应用
数据查找与判断：在许多算法中，需要快速判断一个元素是否存在于集合中。例如，在判断一个数组中是否存在重复元素的算法中，可以使用哈希表来记录每个元素出现的次数。通过将元素作为键，出现次数作为值，遍历数组时，每次将元素在哈希表中的值加 1。如果某个元素在哈希表中的值在加 1 之前已经大于 0，就说明该元素是重复的。这种方法的时间复杂度可以达到O(n)，相比于暴力解法的O(n ² )有很大的性能提升。
图算法：在图算法中，哈希表可以用于存储图的节点和边的信息。例如，在广度优先搜索（BFS）和深度优先搜索（DFS）算法中，需要记录已经访问过的节点，以避免重复访问。可以使用哈希表来存储节点的访问状态，将节点作为键，访问状态（如布尔值）作为值。这样在搜索过程中，能够快速判断一个节点是否已经被访问过，提高搜索效率。

字符串处理：在字符串相关的算法中，哈希表也有广泛的应用。例如，在字符串匹配算法中，如 Rabin - Karp 算法，通过计算字符串的哈希值来快速判断两个字符串是否相等。将模式串的哈希值预先计算出来，然后在文本串中滑动窗口，计算每个窗口内字符串的哈希值并与模式串的哈希值进行比较。如果哈希值相等，再进行字符级别的精确比较，这样可以大大减少比较的次数，提高匹配效率。

下面本文将通过几道与哈希表相关例题！

例题

一、两数之和

1. 题目链接：两数之和
2. 题目描述：

给定⼀个整数数组 nums 和⼀个整数⽬标值 target，请你在该数组中找出和为目标值 target 的那两 个整数，并返回它们的数组下标。 你可以假设每种输⼊只会对应⼀个答案。但是，数组中同⼀个元素在答案⾥不能重复出现。 你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,3], target = 6
输出：[0,1]

3. 解法（哈希表）：
   算法思路：
   • 如果我们可以事先将「数组内的元素」和「下标」绑定在⼀起存入[哈希表」中，然后直接在哈希 表中查找每⼀个元素的 target - nums[i] ，就能快速的找到「⽬标和的下标」。
   • 这⾥有⼀个⼩技巧，我们可以不⽤将元素全部放⼊到哈希表之后，再来⼆次遍历（因为要处理元素 相同的情况）。⽽是在将元素放⼊到哈希表中的「同时」，直接来检查表中是否已经存在当前元素 所对应的⽬标元素（即 target - nums[i] ）。如果它存在，那我们已经找到了对应解，并⽴ 即将其返回。⽆需将元素全部放⼊哈希表中，提⾼效率。
   • 因为哈希表中查找元素的时间复杂度是 O(1) ，遍历⼀遍数组的时间复杂度为 O(N) ，因此可以 将时间复杂度降到 O(N) 。 这是⼀个典型的「用空间交换时间」的方式。

4. 代码示例：

  public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> hash = new HashMap<>(); // <nums[i], i>for (int i = 0; i < nums.length; i++) {int x = target - nums[i];if (hash.containsKey(x)) {return new int[]{i, hash.get(x)};}hash.put(nums[i], i);}// 照顾编译器return new int[]{-1, -1};}

二、判断是否互为字符重排

1. 题目链接：判断是否互为字符重排
2. 题目描述：

给定两个字符串 s1 和 s2 ，请编写⼀个程序，确定其中⼀个字符串的字符重新排列后，能否变成 另⼀个字符串。
示例 1：
输⼊: s1 = “abc”, s2 = “bca”
输出: true
示例 2：
输⼊: s1 = “abc”, s2 = “bad”
输出: false

3. 解法（哈希表）：
   算法思路：
   当两个字符串的⻓度不相等的时候，是不可能构成互相重排的，直接返回 false ；如果两个字符串能够构成互相重排，那么每个字符串中「各个字符」出现的「次数」⼀定是相同 的。因此，我们可以分别统计出这两个字符串中各个字符出现的次数，然后逐个⽐较是否相等即 可。这样的话，我们就可以选择「哈希表」来统计字符串中字符出现的次数

4. 代码示例：

 public boolean CheckPermutation(String s1, String s2) {if (s1.length() != s2.length()) return false;int[] hash = new int[26];// 先把第⼀个字符串的信息统计到哈希表中for (int i = 0; i < s1.length(); i++) {hash[s1.charAt(i) - 'a']++;}// 遍历第⼆个字符串，判断是否可以重排for (int i = 0; i < s2.length(); i++) {hash[s2.charAt(i) - 'a']--;if (hash[s2.charAt(i) - 'a'] < 0) return false;}return true;}

三、存在重复元素 I

1. 题目链接：存在重复元素1
2. 题目描述：

给你⼀个整数数组 nums 。如果任⼀值在数组中出现至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1]
输出：true
示例 2：
输入：nums = [1,2,3,4]
输出：false

3. 解法（哈希表）：
   算法思路： 分析⼀下题目，出现「至少两次」的意思就是数组中存在着重复的元素，因此我们可以无需统计元素 出现的数⽬。仅需在遍历数组的过程中，检查当前元素「是否在之前已经出现过」即可。 因此我们可以利用哈希表，仅需存储数「组内的元素」。在遍历数组的时候，⼀边检查哈希表中是否 已经出现过当前元素，⼀边将元素加⼊到哈希表中

4. 代码示例：

  public boolean containsDuplicate(int[] nums) {Set<Integer> hash = new HashSet<>();for (int x : nums) {if (hash.contains(x)) return true;hash.add(x);}return false;}

四、 存在重复元素 II

1. 题目链接：存在重复元素||
2. 题目描述：

给你⼀个整数数组 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. 解法（哈希表）：
   算法思路： 解决该问题需要我们快速定位到两个信息：
   • 两个相同的元素；
   • 这两个相同元素的下标。 因此，我们可以使用「哈希表」，令数组内的元素做 key 值，该元素所对应的下标做 val 值，将 「数组元素」和「下标」绑定在⼀起，存入到「哈希表」中。

思考题： 如果数组内存在大量的「重复元素」，而我们判断下标所对应的元素是否符合条件的时候，需要将不同下标的元素作比较，怎么处理这个情况呢？ 答：这里运用了⼀个「小贪心」。
我们按照下标「从小到大」的顺序遍历数组，当遇到两个元素相同，并且比较它们的下标时，这两个
下标⼀定是距离最近的，因为：
• 如果当前判断符合条件直接返回 true ，无需继续往后查找。
• 如果不符合条件，那么前⼀个下标⼀定不可能与后续相同元素的下标匹配（因为下标在逐渐变大），那么我们可以大胆舍去前⼀个存储的下标，转而将其换成新的下标，继续匹配。

4. 代码示例：

 public boolean containsNearbyDuplicate(int[] nums, int k) {Map<Integer, Integer> hash = new HashMap<>();for (int i = 0; i < nums.length; i++) {if (hash.containsKey(nums[i])) {if (i - hash.get(nums[i]) <= k) return true;}hash.put(nums[i], i);}return false;}

五、字母异位词分组

1. 题目链接：字母异位词分组
2. 题目描述：

给你⼀个字符串数组，请你将字母异位词组合在⼀起。可以按任意顺序返回结果列表。 字母异位词是由重新排列源单词的字母得到的⼀个新单词，所有源单词中的字⺟通常恰好只用⼀次。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

3. 解法（哈希表 + 排序）：
   算法思路：
   互为字母异位词的单词有⼀个特点：将它们「排序」之后，两个单词应该是「完全相同」的。 所以，我们可以利⽤这个特性，将单词按照字典序排序，如果排序后的单词相同的话，就划分到同⼀ 组中。 这时我们就要处理两个问题：
   • 排序后的单词与原单词需要能互相映射；
   • 将排序后相同的单词，「划分到同⼀组」； 利用语言提供的「容器」的强⼤的功能就能实现这两点：
   • 将排序后的字符串（ string ）当做哈希表的 key 值； • 将字⺟异位词数组（ string[] ）当成 val 值。 定义⼀个「哈希表」即可解决问题

4. 代码示例：

  public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> hash = new HashMap<>();// 1. 先把所有的字⺟异位词分组for (String s : strs) {char[] tmp = s.toCharArray();Arrays.sort(tmp);String key = new String(tmp);if (!hash.containsKey(key)) {hash.put(key, new ArrayList());}hash.get(key).add(s);}// 2. 提取结果return new ArrayList(hash.values());}

结语

本文到这里就结束了，主要介绍了哈希表以及哈希表在算法中的应用，总而言之，在很多题目中，哈希表都是很常见的，它都做为一种很重要的储存数据的容器，希望大家可以有所收获！

以上就是本文全部内容，感谢各位能够看到最后，创作不易，希望大家多多支持！

最后，大家再见！祝好！我们下期见！