优选算法的映射之妙：哈希表专题
专栏：算法的魔法世界
个人主页：手握风云
目录
一、哈希表简介
二、例题讲解
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 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 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 map = new HashMap(); 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>，遍历完一个字符串，符合要求，直接丢进新创建的顺序表中。
完整代码实现：
class Solution { public List<List> groupAnagrams(String[] strs) { Map<String, List> 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()); }}
