【leetcode】记录与查找：哈希表的题型分析

前言

🌟🌟本期讲解关于力扣的几篇题解的详细介绍~~~

🌈感兴趣的小伙伴看一看小编主页：GGBondlctrl-CSDN博客

🔥 你的点赞就是小编不断更新的最大动力                                       

🎆那么废话不多说直接开整吧~~

 

目录

📚️1.两数之和

🚀1.1题目描述

🚀1.2思路分析

🚀1.3代码编写

📚️2.存在重复字符II

🚀2.1题目描述

🚀2.2思路分析

🚀2.3代码编写

📚️3.字母异位词分组

🚀3.1题目描述

🚀3.2思路分析

🚀3.3代码编写

📚️4.总结

 

📚️1.两数之和

前提：作为本篇文章的开头，主要是讲解思路，本题比较简单，大家看看思路就可以了；

🚀1.1题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

大家可能都已经做过这个题了吧~~，因为这是梦的开始 

那么直接开始讲解本题的思路过程吧~~~

🚀1.2思路分析

第一种：暴力

这里的思路有两种，第一种就是暴力枚举，就是两层for循环，直接找到我们对应的下标位置；但是肯定还有更加优秀的解法；当然这里的时间复杂度就是O(N^2)的；

第二种：哈希表

这里我们可以使用哈希表进行优化，即当我们遍历某一个值，要找和等于target的另一个值，那么那个值就是“target - num[ i ]”，没有找到，就将遍历的值存入到我们的哈希表中，找到了就直接返回两个对应的下标；

如下所示：

🚀1.3代码编写

暴力我就不演示了，直接编写我们的哈希表的算法吧~~~

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[]{0,0};}
}

解释：注意了，在哈希表中存储的就是我们要使用的类型，第一个参数就是我们的数组中对应的值，然后就是这个值对应的一个下标；

如果不存在我们要找的值，就将遍历的数以及下标放入到我们的hash表中；

📚️2.存在重复字符II

🚀2.1题目描述

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

如下所示：

就是我们可以发现重复的字符，对应的下标是3 - 0 = 3 <= k；所以就返回true；

那么直接讲解小编的一个思路吧

🚀2.2思路分析

这里和上面的两数之和的思路其实一致，只不过就是我们查找的值不一样了

遍历数组，若遍历到的数字，在哈希表中找不到对应的数，那么就存入hash表中，反之找到了那么就要获取这两个相等的值的下标之差，若下小于等于k值，就是直接返回true；反之就将之存入到我们的哈希表中~~~

 小细节：

即当存在两个值相等后，但是下标之差不符合，那么我们可以存入后者值的下标去覆盖，那么只是符合题意的~~~

🚀2.3代码编写

 具体的代码如下所示：

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

大致和第一题没有什么差别；

📚️3.字母异位词分组

🚀3.1题目描述

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

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

如下所示：

大致就是对于异位词进行分组；

🚀3.2思路分析

异位词：就是同样的组成元素，但是不同排列而成的；

大致的思路就是：

我们将遍历的字符串，进行ascll码值的排序操作；将排序后相等的字符串放在一起即可；

大体的思路如下所示：

即如果遍历到的字符串，进行排序后不存在我们的hash表中，那么存入我们排序后的字符串作为key，然后创建一个新的列表，并将这里的值添加进去；反之存在，那么直接找到对应的Key，然后再添加进入我们的列表中；

🚀3.3代码编写

代码如下所示：

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String,List<String>> hash = new HashMap<>();for(int i = 0;i < strs.length;i++){String s = changeString(strs[i]);if(!hash.containsKey(s)){hash.put(s,new ArrayList());}hash.get(s).add(strs[i]);}return new ArrayList(hash.values());}public String changeString(String s){char[] ch = s.toCharArray();Arrays.sort(ch);String str = Arrays.toString(ch);return str;}
}

直接可以通过Array.sort进行排序，然后返回我们排序过后的字符串~~~

📚️4.总结

其实除了上述使用java库中的hash表，那么其实还有一种我们可以自己创建一个hash数组，主要适用于在数据范围不大的题目中，小编这里就没有演示，大家可以力扣上面刷刷~~~

本期主要讲解了关于hash函数的力扣相关题型

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

存在重复字符II（219. 存在重复元素 II - 力扣（LeetCode））

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

🌅🌅🌅~~~~最后希望与诸君共勉，共同进步！！！

---

💪💪💪以上就是本期内容了， 感兴趣的话，就关注小编吧。

       😊😊  期待你的关注~~~