哈希表在算法题目中的应用（Java）

阅读本书更多章节>>>>

目录

哈希表知识回顾

练习1：存在重复元素

练习2：存在重复元素II

练习3：两数之和

练习4：判定是否互为字符重排

练习5：字母异位词分组

---

在本篇文章中，我们重点讲解哈希表在算法题目中的应用，不会涉及到太多哈希表的概念、原理等知识

首先，我们先来简单回顾哈希表

哈希表知识回顾

哈希表是什么？

哈希表 是一种数据结构，用于存储键值对。通过将键转换为索引来实现快速的数据访问。具体而言，哈希表使用一个哈希函数将键映射到一个特定的索引，然后将值存储在该索引位置上。这样，在查找、插入或删除元素时，可以通过哈希函数直接计算出元素应该存储或者所在的位置，从而实现高效的数据操作。哈希表的查询、插入和删除操作的时间复杂度通常为O(1)。简而言之，哈希表是存储数据的容器，是一种非常高效的数据结构

哈希表有什么作用？

 哈希表主要用于快速存储、查找和删除数据，在解决问题时，通常用于快速查找某个元素

什么时候使用哈希表？

（1）当我们需要 快速查找特定元素、 频繁查找某一个元素 及 确定一个集合中是否存在重复元素 时，可以使用哈希表来存储已经访问过的元素，从而实现快速查找和查重

（2）当需要统计数据中各个元素出现的次数，可以使用哈希表来存储元素及其对应的计数值，快速实现统计和计数

（3）当需要建立两个数据集之间的映射关系时，可以使用哈希表来实现映射

怎么使用哈希表？

（1）使用容器，在解决算法问题时，我们常使用的哈希表容器有两种：HashMap 和 HashSet

（2）使用数组模拟简易哈希表，例如，在数据范围很小的时候，我们可以考虑使用int类型的数组来模拟哈希表

接下来，我们以一些练习来进一步掌握哈希表在算法题目中的应用

练习1：存在重复元素

题目链接：

217. 存在重复元素 - 力扣（LeetCode）

题目描述：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 105-109 <= nums[i] <= 109

思路分析：

 首先我们来分析题目，在整数数组中，若有一个数在数组中出现了两次以上，则返回true，否之，返回false。我们很容易想到暴力解法，即 固定一个元素，然后向后遍历，观察是否有与其相同的元素，其时间复杂度为 O(N ^ 2)，因此，当测试数据量较大时，会超出时间限制

在暴力枚举时，由于我们每次固定一个元素再向后遍历，因此，很多不符合的元素被重复遍历，为了不遍历这些不符合的元素，我们可以考虑使用哈希表来存放这些元素。对于数组中的每个元素，我们将其插入到哈希表中，若在插入前该元素已经存在于哈希表中，则说明存在重复元素

代码实现：

class Solution {    public boolean containsDuplicate(int[] nums) {        Set<Integer> hash = new HashSet<>();        for(int i = 0; i < nums.length; i++{            if(hash.contains(nums[i])){                return true;            }else{                hash.add(nums[i]);            }        }        return false;    }}

练习2：存在重复元素II

题目链接：

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

提示：

1 <= nums.length <= 105-109 <= nums[i] <= 1090 <= k <= 105

思路分析：

 本题的解题思路与练习1类似，但不同的是：在找到两个相同元素时，要判定这两个元素的下标绝对值是否小于等于k。因此，我们既要保存数组元素，还要保存元素下标。

由于数组中同一个元素可能出现两次以上，当判断两个相同元素的数组下标的差（abs(i - j)）大于k时，要将哈希表中的下标更新为当前下标。例如：

代码实现：

class Solution {    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]) && (i - hash.get(nums[i]) <= k)){                return true;            }else{                hash.put(nums[i], i);            }        }        return false;    }}

练习3：两数之和

题目链接：

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只会存在一个有效答案

思路分析：

本题要求我们在整数数组中找到两个元素，这两个元素的和为target，本题与练习1的解题思路类似，我们可以使用哈希表来存放整数数组中的元素及其下标，在哈希表中寻找是否存在元素 target - nums[i]，需要注意的是，若我们先将数组中所有元素和下标都存放在哈希表中，然后再遍历数组，查找哈希表中是否存在元素 target - nums[i]，此时可能会出现同一个元素在答案中重复出现的情况（例如：target = 8，nums = [1, 2, 4, 3]，当前元素nums[2] = 4，由于数组中所有元素及下标已经放在哈希表中，因此此时元素4存在于哈希表中，但其下标与当前下标相同，即一个元素在答案中重复出现）

因此，若我们先将数组中所有元素和下标放入哈希表时，在查找哈希表中是否存在元素 target - nums[i]时，还需要判断其下标是否与当前下标相同

我们还可以边遍历数组，边向数组中存放元素，此时，哈希表中存放的元素为 nums[i]之前的元素，查找当前元素之前是否存在元素 = target - nums[i]，这样，就不需要对下标进行判断了

代码实现：

class Solution {    public int[] twoSum(int[] nums, int target) {        for(int i = 1; i < nums.length; i++){            for(int j = i - 1; j >= 0; j--){                if(nums[i] + nums[j] == target){                    return new int[] {i, j};                }            }        }        return null;    }}

练习4：判定是否互为字符重排

题目链接：

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

题目描述：

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

示例 1：

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

示例 2：

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

说明：

0 <= len(s1) <= 100 0 <= len(s2) <= 100

思路分析：

题目要求我们判断字符串s1和s2是否 是s1中的字符重新排列后，变为s2。若s1中的字符能够重新排列成s2，则s1中的字符与s2中的字符相同。要想保证两字符串字符相同，首先两字符串的长度必须相同，因此，我们先判断两字符串长度是否相同，若相同，我们再来判断其中字符是否都相同。

我们可以使用哈希表来保存字符及其出现的次数，先遍历s1，保存其所有的字符及其出现的次数，再遍历s2，若当前字符不在哈希表中，则两字符串中存在不相同的字符，直接返回false；若当前字符在哈希表中，则次数 - 1，若次数 - 1 之后为 -1，则说明当前字符出现次数大于 s1中出现次数，两字符串字符不完全相同，返回false。若完成遍历，则说明两字符串中的字符完全相同，返回true

由于两个字符串中的字符都是由小写字母构成的，因此，我们可以使用数组来模拟哈希表，创建一个大小为26的int类型数组，下标表示字符（例如 a 对应下标 0，b对应下标 1...）而元素表示字符的出现次数

代码实现：

class Solution {    public boolean CheckPermutation(String s1, String s2) {        if(s1.length() != s2.length()) return false;//先判断长度是否相同        if(s1 == null) return true;//若两字符串都为空，则直接返回true        int[] hash = new int[26];//使用int数组模拟哈希表        for(int i = 0; i < s1.length(); i++){//先遍历s1，将字符及其出现次数存放在哈希表中            hash[s1.charAt(i) - 'a']++;        }        for(int i = 0; i < s2.length(); i++){//再遍历s2，判断两字符是否相同           if(--hash[s2.charAt(i) - 'a'] < 0) return false;         }        return true;    }}

练习5：字母异位词分组

题目链接：

49. 字母异位词分组 - 力扣（LeetCode）

题目描述：

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]输出: [[""]]

示例 3:

输入: strs = ["a"]输出: [["a"]]

提示：

1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i] 仅包含小写字母

思路分析：

字母异位词与 练习4 中的 字符重排 相同，即 两个字符串中的所有字符相同。题目要求我们将所有 字母异位词组合在一起，即将 所有字符相同的字符串放在一个集合中

首先，我们解决第一个问题：如何判断字母异位词？

在 练习4 中，我们使用数组模拟的哈希表来判断两个字符串是否互为字符重排，但在本题中，我们不能继续使用这种方式来判断字母异位词，因为本题中存在许多组字母异位词，若通过这种方式来判断字母异位词，则每次都需要遍历不同组字母异位词和当前字符串。在这里，我们可以考虑将字符串按照 ASCII码值进行升序排列，（例如：eat 排列后 为 aet，tea排列后 为 aet）此时，只需要判断排列后的字符串是否相同，即可判断出两个字符串是否为同一组字母异位词

接下来，我们解决第二个问题：如何将字母异位词组合在一起？

 哈希表可以统计数据中各个元素出现的次数，使用哈希表可以存储元素及其对应的计数值，在这里，我们可以使用哈希表 存储 排列后的字符串 及其 字母异位词，即 key：存储排列后的字符串，value：存储 List，其中存放的元素类型为 String，这样，就可以将字母异位词存放在List中 

因此，我们只需要遍历字符串数组，将其按照ASCII码值进行升序排列，然后判断排列后的字符串是否已经存在于哈希表中，若存在，则将 字母异位词 放入List中；若不存在，则创建新的ArrayList

代码实现：

class Solution {    public List<List<String>> groupAnagrams(String[] strs) {        Map<String, List<String>> hash = new HashMap<>();        for(String str: strs){            char[] chs = str.toCharArray();            Arrays.sort(chs);            String key = new String(chs);            List list = hash.getOrDefault(key, new ArrayList<String>());            list.add(str);            hash.put(key, list);        }        return new ArrayList<List<String>>(hash.values());    }}

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-03-27/149765.html，文章来源：网络cs，作者：亙句，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！