哈希表 算法专题
哈希表简介
- 是什么
存储数据的容器 - 有啥用?
"快速"查找某个元素 - 什么时候用哈希表
频繁地查找某个数(有序用二分) - 怎么用哈希表
- 容器
- 用数组模拟
字符串中的字符
范围比较小的数
一. 两数之和
两数之和
class Solution {public int[] twoSum(int[] nums, int target) {//固定一个数, 找其他的数和其相加是否等于target//那么就可以转换成://固定一个数i, 找到其他的数是否有target-i//那么,频繁地找一个数, 想到可以使用hash表//固定一个数, 判断这个数之前是否有target-i, 即在哈希表中找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 null;}
}
二. 判断是否互为字符重排
判断是否互为字符重排
class Solution {public boolean CheckPermutation(String s1, String s2) {//判断每个字符出现的个数是否相同即可//1. 先判断字符串长度是否相等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']++;}//判断s2的情况for(int i = 0; i < s2.length(); i++){hash[s2.charAt(i) - 'a']--;if(hash[s2.charAt(i) - 'a'] < 0){return false;}}return true;}
}
三. 存在重复元素
存在重复元素
//思路和两数之和类似
class Solution {public boolean containsDuplicate(int[] nums) {Set<Integer> hash = new HashSet<>();for(int x : nums){if(hash.contains(x)) return true;hash.add(x);}return false;}
}
四. 存在重复元素II
存在重复元素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]) && i - hash.get(nums[i]) <= k) {return true;}hash.put(nums[i], i);}return false;}
}
五. 字母异位词分组
字母异位词分组
class Solution {public List<List<String>> groupAnagrams(String[] strs) {//排序后相同的单词属于同一组//<排序后, 排序前[]>//结果返回所有的value即可Map<String, List<String>> hash = new HashMap<>();for(String x : strs){char[] tmp = x.toCharArray();Arrays.sort(tmp);String key = new String(tmp);if(!hash.containsKey(key)){hash.put(key, new ArrayList());}hash.get(key).add(x);}return new ArrayList(hash.values());}
}
```\