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

迈不过友情╰ 2024-04-25 08:44 62阅读 0赞

**目录**

哈希表知识回顾

练习1：存在重复元素

练习2：存在重复元素II

练习3：两数之和

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

练习5：字母异位词分组

--------------------

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

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

## 哈希表知识回顾 ##

> **哈希表是什么？**

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

> **哈希表有什么作用？**

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

> **什么时候使用哈希表？**

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

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

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

> **怎么使用哈希表？**

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

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

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

## 练习1：存在重复元素 ##

**题目链接：**

[217. 存在重复元素 - 力扣（LeetCode）][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）][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] <= 109`
 *  `0 <= k <= 105`

**思路分析：**

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

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

![0da95aeec70b46f5bbf80e164124e17c.png][]

**代码实现：**

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）][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）][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）][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 <= 104`
 *  `0 <= strs[i].length <= 100`
 *  `strs[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());
        }
    }

[217. _ - _LeetCode]: https://leetcode.cn/problems/contains-duplicate/description/
[219. _ II - _LeetCode]: https://leetcode.cn/problems/contains-duplicate-ii/description/
[0da95aeec70b46f5bbf80e164124e17c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/5c694bd8d99d4d08b698b5c8d21edfe4.png
[1. _ - _LeetCode]: https://leetcode.cn/problems/two-sum/description/
[01.02. _ - _LeetCode]: https://leetcode.cn/problems/check-permutation-lcci/description/
[49. _ - _LeetCode]: https://leetcode.cn/problems/group-anagrams/description/