【算法专场】哈希表

前言

当我们想要快速查找某个值是否存在，或者想要对数据进行去重的时候，我们有没有方法可以解决上面这些问题？我们可以用哈希表。

哈希表

哈希表（Hash Table）是一种通过哈希函数将键（key）映射到表中位置来访问记录的数据结构，它具有高效的数据查找、插入和删除能力。

我们什么时候可以使用哈希表？

在快速查找、频繁统计、快速映射、去重的情景下都可以使用哈希表。

我们来通过算法题目来更好的了解哈希算法。

1. 两数之和 - 力扣（LeetCode）

算法分析

本道题要求我们从数组中找两个数，并且两数之和为target。这道题可以采用暴力枚举，时间复杂度为O(n^2)，如果在大量数据的情况下，是会超时的，那么我们可以采用哈希算法来解决这道题。

我们可以在hash表中存储元素以及其下标的映射。在遍历数组的过程，每次判断（target-当前元素）是否在hash表中存在，如果不存在，那就将

当前元素以及其下标存到hash表中，反之，如果找到，那么就取出下标返回。

为什么不将所有元素都放进去hash表再进行判断？这样的话就无法解决元素重复的问题。假设目标值为2，那么现在有1，我们如果将1先放进了hash表，那么我们在遍历的时候，可以找到1，但实际上这两个1是同一个。而如果我们先判断hash表中是否存在（target-当前元素）的元素，则可以避免出现重复的情况。

算法代码

/*** 解决方案：找出数组中两个数之和等于目标值的数对索引* 方法：使用哈希表实现* 时间复杂度：O(n)，其中n是数组的长度* 空间复杂度：O(n)，需要额外的空间来存储哈希表* * @param nums 输入的整数数组* @param target 目标值，寻找两数之和等于此值* @return 返回一个长度为2的整数数组，包含满足条件的两个数的索引；如果不存在这样的数对，则返回{-1, -1}*/
public int[] twoSum(int[] nums, int target) {// 利用哈希表来存储已经遍历过的数字及其索引，以便快速检查目标值与当前值的差值是否已经出现过HashMap<Integer,Integer> map=new HashMap<>();for(int i=0;i<nums.length;i++){// 检查当前数字与目标值的差值是否已经在哈希表中if(map.containsKey(target-nums[i])){// 如果差值存在，则找到了满足条件的两个数，返回它们的索引return new int[]{map.get(target-nums[i]),i};}else{// 如果差值不存在，将当前数字及其索引放入哈希表中，以供后续查找使用map.put(nums[i],i);}}// 如果遍历完整个数组后仍未找到满足条件的数对，返回{-1, -1}return new int[]{-1,-1};
}

时间复杂度为O(n),空间复杂度为O(n).

面试题 01.02. 判定是否互为字符重排

算法分析

本道题其实就是要判断两个字符串是否是一样，那么我们就可以两个hash表，来存储每次字符出现的次数，如果两个hash表对应的值都相等，那就说明两个字符串是一样的。

算法代码

    /*** 检查两个字符串是否互为字符重排* * @param s1 第一个字符串* @param s2 第二个字符串* @return 如果两个字符串互为字符重排，则返回true；否则返回false*/public boolean CheckPermutation(String s1, String s2) {// 如果两个字符串长度不同，则它们不可能互为字符重排if (s1.length() != s2.length()) {return false;}// 如果任一字符串为空，则它们不可能互为字符重排if (s1.length() == 0 || s2.length() == 0) {return false;}// 创建一个哈希表来存储字符出现的次数，ASCII码共有128个字符，额外留一个位置给可能的空字符int hash[] = new int[129];// 遍历第一个字符串，统计每个字符出现的次数for (int i = 0; i < s1.length(); i++) {char ch = s1.charAt(i);hash[ch]++;}// 遍历第二个字符串，检查每个字符是否在哈希表中出现过，并减少相应字符的计数for (int i = 0; i < s2.length(); i++) {char ch = s2.charAt(i);// 如果字符在哈希表中的计数为0，则说明两个字符串的字符组成不同if (hash[ch] == 0) {return false;}hash[ch]--;}// 如果所有字符都能一一对应，且没有多余的字符，则两个字符串互为字符重排return true;}

217. 存在重复元素

算法分析

这道题就是要求在数组中有没有一个元素是出现超过两次的，我们可以用哈希算法来解决这道题，利用HashSet，如果set里面没有存在当前元素，就将当前元素存到set中；反之，如果有，则返回true。

算法代码

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

219. 存在重复元素 II

算法分析

跟上一道题类似，不过这里还需要将下标进行存储，需要利用HashMap，在遍历的过程中，如果当前元素在hashmap中已经存在，那么就判断这两个元素之间的距离，如果小于k，则返回true，否则将当前元素以及其下标存储到hashmap中。

算法代码

/*** 检查数组中是否存在两个相同的数字，且它们的索引之差的绝对值最大为k* 这个方法通过使用HashMap来跟踪数字及其最后出现的索引来实现* 如果发现重复数字，并且它们的索引之差不超过k，则返回true* 如果不满足这些条件，则在遍历完整个数组后返回false* * @param nums 输入的整数数组* @param k 索引之差的绝对值的最大允许值* @return 如果找到至少一对索引之差的绝对值不超过k的相同数字，则返回true；否则返回false*/public boolean containsNearbyDuplicate2(int[] nums, int k) {// 使用HashMap来存储数字及其对应的索引HashMap<Integer, Integer> map = new HashMap<>();for(int i=0;i<nums.length;i++){// 检查当前数字是否已经在HashMap中存在if(map.containsKey(nums[i])){// 如果当前数字已存在，并且当前索引与之前索引之差不超过k，则返回trueif(i-map.get(nums[i])<=k){return true;}}// 更新或添加当前数字及其索引到HashMap中map.put(nums[i],i);}// 如果没有找到满足条件的数字对，则返回falsereturn false;}

时间复杂度为O(n),空间复杂度为O(n)

解法二

对于这道题，我们还可以通过滑动窗口的思想来解决，题目要求在数组中找两个相同的元素，并且他们下标的距离要小于等于k，那么我们就可以通过维护一个长度为k的窗口。如果当窗口小于k的时候，那么我们就将元素添加到窗口中，如果窗口中存在和当前元素相同的元素，那么就直接返回true，反之，则将元素添加到窗口中，当元素的个数等于窗口的长度的时候，那就将左边第一个元素进行移除。这里我们借助HashSet来判断窗口中是否有重复的元素。

算法代码

  /*** 检查数组中是否存在重复的元素，且它们的索引之差的绝对值最大为k* 这个方法用于识别在一定索引范围内是否存在重复的数字** @param nums 一个整数数组，其中可能包含重复元素* @param k 索引之差的绝对值的最大允许值* @return 如果找到至少一对索引之差的绝对值不超过k的重复元素，则返回true；否则返回false*/public boolean containsNearbyDuplicate(int[] nums, int k) {// 使用HashSet存储当前窗口内的元素，以便快速检查重复Set<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {// 当窗口大小超过k时，移除窗口最左侧的元素，以保持窗口大小不超过kif (i > k) {set.remove(nums[i - k - 1]);}// 尝试将当前元素添加到HashSet中如果添加失败，说明存在重复元素，且索引之差不超过kif (!set.add(nums[i])) {return true;}}// 遍历完成后，如果没有返回true，说明没有找到满足条件的重复元素return false;}

算法分析

这道题相对于前面两道题来说，要难上一些。但是以及依旧可以借鉴上面题目的思想，利用滑动窗口+有序集合。

根据题意，假设任意位置为i，值为u。我们希望在下标范围为[max(0,i-k）,i)的范围内找到值范围在[u-t,u+t]范围内的数。如果我们每次遍历到任意位置的时候，都往前检查k个元素，这样时间负责度会达到O(nk)，会超时，所以我们需要对检索后面k个元素进行优化，在java中，有一个TreeSet数据结构，能够帮助我们在有序集合内快速找到值小于等于u或者大于等于u的值。

算法代码

/*** 检查数组中是否存在两个索引之差不超过indexDiff且值之差不超过valueDiff的元素* * @param nums 包含整数的数组* @param indexDiff 索引之间的最大差值* @param valueDiff 值之间的最大差值* @return 如果找到满足条件的元素对，则返回true；否则返回false*/public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {int n = nums.length;TreeSet<Integer> set = new TreeSet<>();for(int i=0;i<n;i++){int u=nums[i];//如果set不为空，从set中找到大于等于u的最小值（最接近u的数）Integer ceil = set.ceiling(u);//如果set不为空，且小于等于u的最大值（最接近u的数）Integer floor = set.floor(u);//检查是否存在满足条件的元素if(ceil!=null&&ceil-u<=valueDiff) return true;if(floor!=null&&u-floor<=valueDiff) return true;//将当前元素加入setset.add(u);//如果当前索引大于等于indexDiff，则从set中移除滑动窗口最左侧的元素if(i>=indexDiff) set.remove(nums[i-indexDiff]);}//遍历后仍未找到满足条件的元素，返回falsereturn false;}

49. 字母异位词分组

算法分析

这道题要我们找字符串的字符个数都相同的字符串，并将这些字符串都放在同一个列表中，那么我们可以采用哈希算法，这里借助HashMap，键key为字符串，值为一个存储着字符串的列表。在遍历字符串数组的时候，我们每次将字符串进行排序，再判断hashmap是否存储当前字符串，如果存在，则将当前元素添加到列表中，反之，则创建一个列表，并将当前元素添加到列表中。最后再将map中的值存储放到ans中。

算法代码

/*** 对字符串数组进行遍历，将其中的字符串转换为字符数组并排序，然后转换回字符串* 使用HashMap来存储这些转换后的字符串作为键，以及它们在原始数组中的出现情况作为值* 最后，将HashMap中的所有值收集到一个二维列表中并返回* * @param strs 字符串数组，包含待处理的字符串* @return 返回一个二维列表，其中包含按照字母异位词分组的字符串列表*/
public List<List<String>> groupAnagrams(String[] strs) {// 初始化答案列表List<List<String>> ans=new ArrayList<>();// 初始化哈希图，用于存储排序后的字符串作为键，以及它们的出现情况作为值HashMap<String,List<String>> map=new HashMap<>();// 遍历输入的字符串数组for(int i=0;i<strs.length;i++){// 获取当前遍历到的字符串String s=strs[i];// 将字符串转换为字符数组char[] chars=s.toCharArray();// 对字符数组进行排序Arrays.sort(chars);// 将排序后的字符数组转换回字符串s=new String(chars);// 如果排序后的字符串已经在哈希图中存在if(map.containsKey(s)){// 将当前字符串添加到该键对应的列表中map.get(s).add(strs[i]);}else{// 否则，创建一个新的字符串列表List<String> list=new ArrayList<>();// 将当前字符串添加到列表中list.add(strs[i]);// 将排序后的字符串和对应的字符串列表作为键值对存入哈希图map.put(s,list);}}// 遍历哈希图的所有键for(String key:map.keySet()){// 将每个键对应的值（字符串列表）添加到答案列表中ans.add(map.get(key));}// 返回答案列表return ans;
}