优选算法的映射之妙：哈希表专题

专栏：算法的魔法世界

个人主页：手握风云

目录

一、哈希表简介

二、例题讲解

2.1. 两数之和

2.2. 判定是否互为字符重排

2.3. 存在重复元素

2.4. 存在重复元素 II

2.5. 字母异位词分组

---

一、哈希表简介

• 哈希表

        哈希表（Hash Table）是一种高效的数据结构，通过 “键 - 值”（Key-Value）对的形式存储和检索数据。

• 作用

        利用哈希函数将键映射到数组中的特定位置，从而实现快速查找、插入和删除操作。查找、插入、删除操作的时间复杂度均为 O(1)，因为哈希函数能直接定位数据位置。

• 什么时候用哈希表

        当我们需要频繁查找某一个元素的时候，效率非常高。

• 怎么用哈希表

        在Java的集合框架中基于哈希表实现的HashMap和HashSet。但是新建哈希表和调用接口都是有时间消耗。如果说要处理的数据是字符，或者数据范围比较小的int型时，我们可以使用数据模拟哈希表。比如字符，我们可以利用ASCII码值映射到数组的下标。

二、例题讲解

2.1. 两数之和

        给定一个整数数组 nums 和一个整数目标值 target，在数组中找到和等于 target 的两个不同元素，返回这两个元素的数组下标。

        这个题的暴力枚举思想很简单，先固定其中一个数，然后依次与前面的数字进行相加，这样能做到不重不漏。时间复杂度。

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

        接下来使用哈希表进行优化：当我们固定nums[i]的时候，我们需要在前面寻找target - nums[i]，那我们就可以先遍历数组，把数组元素丢进哈希表，再让指针向后移动，如果能找到target - nums[i]，就直接返回下标，没找到就继续向后移动。我们还需要判断一种情况，就是如果x == target - nums[i]，就会自己找到自己。

        完整代码实现：

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> hash = new HashMap<>();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};}
}

2.2. 判定是否互为字符重排

        判断其中一个字符串通过字符重新排列后，能否完全变成另一个字符串（即两字符串本质是 “字符组成与个数完全相同，仅顺序不同”）。

        如果两个字符串长度不相等，直接返回false。我们可以先枚举出s1所有的重排结果，再与s2进行比较，但这样的时间复杂度会达到指数级别。此时我们就可以利用哈希表来统计每个字符出现的次数，比较两个哈希表中每个字符出现的次数是否相同。这时我们就可以借助字符的ASCII码值，利用数组模拟哈希表。在此基础上，我们还可以优化，只利用一个哈希表就行：先遍历字符串s1，将s1中的字符丢进哈希表，再去遍历s2，出现的字符则减少，如果hash[s2.charAt(i) - 'a'] < 0，返回false。

class Solution {public boolean CheckPermutation(String s1, String s2) {if (s1.length() != s2.length()) {return false;}int[] hash = new int[26];// 统计s1中每个字符出现的次数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;}
}

2.3. 存在重复元素

        判断数组中是否存在重复元素。

        创建一个哈希表，遍历数组，如果哈希表中存在该元素，返回true；没有，则丢进哈希表。

        完整代码实现：

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

2.4. 存在重复元素 II

        与上一题不同的是，找出相等元素，索引距离不超过 k。

        遍历数组，如果哈希表中不存在该元素，则将它本身和下标一起丢进哈希表中，如果存在，在判断索引距离是否<=k。如果后面还存在重复元素，我们可以直接覆盖，因为我们要找的是距离最近的重复元素。

        完整代码实现：

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

2.5. 字母异位词分组

        给定一个字符串数组，需将其中的字母异位词（字母种类、数量完全相同，仅排列顺序不同的字符串）归为一组，最终返回包含所有分组的列表。

        我们需要先判断这些单词是否为字母异位词，我们这里可以我们利用字符的ASCII码值进行排序。对于字符串的分组，我们可以将哈希表的键值对类型定义为HashMap<String, List<String>>，遍历完一个字符串，符合要求，直接丢进新创建的顺序表中。

        完整代码实现：

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> hash = new HashMap<>();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);}return new ArrayList<>(hash.values());}
}