哈希表 算法专题

哈希表简介

1. 是什么
   存储数据的容器
2. 有啥用?
   "快速"查找某个元素
3. 什么时候用哈希表
   频繁地查找某个数(有序用二分)
4. 怎么用哈希表

• 容器
• 用数组模拟
  字符串中的字符
  范围比较小的数

一. 两数之和

两数之和

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());}
}
```\