🍍1. 刷题与观看须知
任何算法题目，你光看不自己去实现，都不算真正地学到了自己的知识库中。所以推荐兄弟们有空要通过题目链接一定要去自己尝试写。而且即使做出来了，也要去想办法优化自己的代码，即使是同样的方法，也许别人写的更加简洁易懂。也要去学习复杂度更低更优秀的解题方法，正所谓条条大路通罗马，我走了较远的那条路，但我们到了终点也该学习一下更短的路，不然下次仍然会走最远的路，这就脱离了学习的本质了。
🍍2. 力克哈希，鏖战力扣
🐄1.存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
题目链接：存在重复元素https://leetcode-cn.com/problems/contains-duplicate/
题目分析：这个题目的名称，就已经是用哈希的标志了，拿这道题作为哈希的入门实在是最好不过了，哈希经典的以空间换时间（升高空间复杂度降低时间复杂度）。我也贴上排序做法的代码供大家对比。
方法1：排序
时间复杂度O(nlongn)：主要是排序的开销，如果是朴素的两层for循环暴力遍历开销为O(n^2)
空间复杂度O(nlogn)：排序的开销
class Solution { public boolean containsDuplicate(int[] nums) { //排序 Arrays.sort(nums); int n=nums.length; //看相邻的是否相等 for(int i=0;i<n-1;i++){ if(nums[i]==nums[i+1]){ return true; } } return false; } }
方法2：哈希判重
复杂度O(n):n为nums的长度，主要是循环的耗时
复杂度O(n):n为nums的长度，主要是哈希的开销，最差的情况下数组全部都被放入set中
class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> set=new HashSet<Integer>(); int n=nums.length; for(int i=0;i<n;i++){ if(!set.contains(nums[i])){ set.add(nums[i]); }else{ return true; } } return false; } }
🐏2.存在重复元素||
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
题目链接：存在重复元素|| https://leetcode-cn.com/problems/contains-duplicate-ii/
题目分析：这道题是第一题的进阶，在第一题的要求上做了一定的要求，更加适合哈希的做法，因为涉及到索引，我们需要把set转换成map，key保存值，value保存下标索引。
方法1：哈希判重
时间复杂度O(n)：n为nums的长度，主要是循环的耗时，最差情况整个数组遍历完。
空间复杂度O(n)：n为nums的长度，主要为哈希的开销
class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { //key存值,value存下标 Map<Integer,Integer> map=new HashMap<>(); int n=nums.length; for(int i=0;i<n;i++){ //没有这个数，存入map中 if(!map.containsKey(nums[i])){ map.put(nums[i],i); }else{ //不满足题目的要求 if(map.get(nums[i])-i>k||i-map.get(nums[i])>k){ //更新下标,防止这个数后面再出现就满足要求了 map.put(nums[i],i); }else{ //满足要求返回true return true; } } } //结束完说明没有返回false return false; } }
🐠3.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
题目链接：有效的字母异位词https://leetcode-cn.com/problems/valid-anagram/
题目解析：这道题目的意思很简单，就是字符串出现的字母和频率都相同即可，这是非常经典的使用哈希的特征。但这里我想让大家知道，排序才是最简单的方法，也是大家都应该想到的。不仅是数字可以排序，字母也是可以排序的，如果是有效的字母异位词，排序后的char[]肯定一模一样。但是大家一定要知道。既然是哈希专场，利用哈希大家也一定要会做。
方法1：转换为char[]排序后进行对比。
时间复杂度O(nlogn)：排序的时间是O(nlogn)，遍历的世界是O(n)，加起来还是算O(nlogn)
空间复杂度:O(logn)。排序API需要O(logn)的复杂度，而且如果是Java语言的话，由于String的不可变性，还得再用O(n)的空间来拷贝数组。
class Solution { public boolean isAnagram(String s, String t) { //先将字符串都转换为字符数组 char[] arr1=s.toCharArray(); char[] arr2=t.toCharArray(); //sort函数也可以传入字符数组 Arrays.sort(arr1); Arrays.sort(arr2); //Arrays有一个重写的equals方法 //可以直接比较两个数组是否完全一样 return Arrays.equals(arr2,arr1); } }
方法2：利用数组来映射哈希。我们要知道数组也是哈希的提现，索引下标相当于key，存储的值相当于value。我们可以用一个长度为26的char数组来存在从a到z每个数字出现的频率，在遍历s时遇到的每个字符出现的次数+1，遍历t时减1。如果最后数组中不全为0则说明不是有效的字母异位词。
时间复杂度O(n)：n为较长一条字符串的长度，主要是遍历
空间复杂度O(1)：常数级的数组消耗也只算O(1)
class Solution { public boolean isAnagram(String s, String t) { //从下标0存储a开始来存储每个数字出现的频率 int[] arr=new int[26]; //遍历字符串s for(int i=0;i<s.length();i++){ //s.charAt(i)-'a'是为了找到每个字符对应的索引下标 arr[s.charAt(i)-'a']++; } for(int i=0;i<t.length();i++){ arr[t.charAt(i)-'a']--; } //遍历到不为0的说明有字母数量不相等，返回false for(int i=0;i<arr.length;i++){ if(arr[i]!=0) return false; } //遍历结束没返回false说明是有效的字母异位，返回true return true; } }
