💕"白昼之光，岂知夜色之深。"💕
作者：Mylvzi
文章主要内容：算法系列–哈希表
今天为大家带来的是
算法系列--哈希表
1.两数之和
链接:
https://leetcode.cn/problems/two-sum/submissions/515941642/
分析:
有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。
最容易想到的思路就是暴力解法,每遍历到一个数字,就去从头遍历看有没有相加符合条件的数字,但是这样的时间复杂度达到了O(N^2),使用哈希表可以降低到O(N)
之所以是n^2是因为我么在查找第二个数的时候又套了一层for循环,既然涉及到在一堆数中快速查找某一个数,就可以使用hash表进行优化,思路如下:
- 每遍历到一个数,就将其数值和下标存入到哈希表之中
- 判断哈希表中是否存在
target-nums[i]的数字,如果有返回这两个数的下标,如果没有继续遍历
代码:
class Solution { public int[] twoSum(int[] nums, int target) { // 使用哈希表建立数字与下标之间的映射关系 Map<Integer,Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { // 去看是否包含target-i if(map.containsKey(target-nums[i])) { return new int[]{map.get((target-nums[i])),i};// 返回下标 } map.put(nums[i],i); } return null; } }
2.判断是否互为字符重排
链接:
https://leetcode.cn/problems/check-permutation-lcci/description/
分析:
本题最直观的想法就是创建出两个哈希表,分别存储字符串中的所有内容,最后判断两个哈希表是否相同即可
代码:
class Solution { public boolean CheckPermutation(String s1, String s2) { if(s1.length() != s2.length()) return false; Map<Character,Integer> hash1 = new HashMap<>(); Map<Character,Integer> hash2 = new HashMap<>(); for(char c1 : s1.toCharArray()) { hash1.put(c1,hash1.getOrDefault(c1,0) + 1); } for(char c2 : s2.toCharArray()) { hash2.put(c2,hash2.getOrDefault(c2,0) + 1); } return hash1.equals(hash2); } }
注意本题还可以使用排序的思想,将两个字符串进行排序,然后直接判断是否相同即可
class Solution { public boolean CheckPermutation(String s1, String s2) { if (s1.length() != s2.length()) return false; char[] ss1 = s1.toCharArray(); char[] ss2 = s2.toCharArray(); Arrays.sort(ss1); Arrays.sort(ss2); return Arrays.equals(ss1, ss2); } }
只有使用Arrays.equals()这个方法才能判断数组中的内容是否相同,因为里面重写了equals方法,如果直接比较,比较的是地址
3.存在重复元素 I
链接:
https://leetcode.cn/problems/contains-duplicate/description/
分析:
使用set来判断是否出现重复元素
代码:
class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(); for(int n : nums) {// add()的返回值是布尔类型 if(!set.add(n)) return true; } return false; } }
注意: add()的返回值是布尔类型,用于表示此次添加是否成功.set具有去重的功能,如果添加的元素已经存在,就会添加失败
4.存在重复元素 II
链接:
分析:
结合题意解决即可
代码:
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]) && Math.abs(hash.get(nums[i]) - i) <= k) return true; hash.put(nums[i],i); } return false; } }
5.字⺟异位词分组
链接:
https://leetcode.cn/problems/group-anagrams/description/
分析:
本题更像是一道语法题,充分利用了java 的Map容器,相同的字母异位词指的是两个字符串中所包含的字符完全相等,也就是将他们按照ascii码值排序之后得到的结果完全相同,我们设这个排序之后的结果为pivot,那么我们就可以利用哈希表建立<pivot,List<String>>之间的映射关系
- 对字符串进行排序,得到其pivot
- 如果哈希表中不存在pivot,就新创建一个;如果存在,得到pivot对应的list,让其添加当前的字符串
代码:
class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String,List<String>> hash = new HashMap<>(); // 先对所有的字符串进行异或分组 for(String str : strs) { char[] tmp = str.toCharArray(); Arrays.sort(tmp);// 排序 得到pivot String key = new String(tmp);// 转化为字符串 List<String> list = hash.getOrDefault(key, new ArrayList<String>());// 注意有可能不存在 list.add(str);// 添加上当前的字符串 hash.put(key,list);// 插入哈希表 } return new ArrayList(hash.values());// 注意这个语法!可以直接返回hash的所有value的集合 } }
总结:
哈希表的使用场景
- 快速的寻找某一个元素
- 记录出现的次数
哈希表的优化:
- 使用数组来模拟哈希表,往往出现在数据量较小的时候,省去了new()和方法调用的时间
