一、简介
哈希表就是一个使用键值对key-value来存储数据的容器。
用于快速查找某个元素O(1)时间复杂度。
- 应用场景：
频繁查找元素的时候。 - 使用方法
-
- 语言自带的集合类
-
- 使用数组模拟，用下标来当key值。
二、两数之和
题目链接：1.两数之和
题目描述：
解题思路：
- 使用一个hash容器，将数组以数组元素-下标的形式存储起来，
- 再遍历数组，当hash表中有与当前数组元素加起来等于target的并且不是同一个元素的返回即可。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(n)
import java.util.*;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hash = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
hash.put(nums[i], i);
}
for(int i = 0; i < nums.length; i++) {
int j = hash.getOrDefault(target-nums[i], -1);
if(j != -1 && i != j) {
return new int[]{i,j};
}
}
return null;
}
}
三、⾯试题 01.02.判定是否互为字符重排
题目链接：⾯试题 01.02.判定是否互为字符重排
题目描述：
题目解析：
- 判断两个只含有小写字母的字符串，内容在排列之后是否相等
解题思路：
- 使用一个数组，下标表示字符串的元素，数组元素表示每个元素的个数。
- 先遍历一个字符串，将元素与个数存入数组中，
- 再遍历另一个字符串，将数组中对应元素个数抵消。
- 最后看数组中是否全部为0即可。
- 优化思路：
- 当数组中出现小于0的数组元素的时候，就代表该下标对应的字符在两个字符串中个数不一样。
- 两个字符串长度不一样直接就返回false
- 当有上一条条件的时候，就不用在遍历数组了。
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public boolean CheckPermutation(String s1, String s2) {
if(s1.length() != s2.length()) return false;
int[] hash = new int[26];
for(int i = 0; i < s1.length(); i++)
hash[s1.charAt(i) -'a']++;
for(int i = 0; i < s2.length(); i++)
if(--hash[s2.charAt(i)-'a'] < 0)
return false;
return true;
}
}
四、217.存在重复元素
题目链接：217.存在重复元素
题目描述：
解题思路：
- 直接将数组中的元素，放入集合之中
- 遍历数组，当集合中已经有该元素，符合题目条件，返回true
- 如果没有，就将该元素放入集合。
- 当遍历完数组，还没有找到，就返回false
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> hash = new HashSet<>();
for(int i = 0; i < nums.length; i++) {
if(hash.contains(nums[i])) return true;
hash.add(nums[i]);
}
return false;
}
}
五、219.存在重复元素 II
题目链接：219.存在重复元素 II
题目描述：
解题思路：
- 我们将 ( 数组元素 - 下标) 放入hash表中，
- 当我们遍历数组的时候，当集合中已经有该元素，并且下标差值小于等于k，符合题目条件，返回true
- 否则，将该元素以及下标放入hash表中，因为我们求得是小于等于k，所以就算关键字已经存在，那么覆盖后是后一个元素的下标，离下一个该数组元素更近。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(n)
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;
}
}
六、49.字⺟异位词分组
题目链接：49.字⺟异位词分组
题目描述：
题目解析：
- 将给的字符串数组中，元素排列之后相等的元素放在一堆
解题思路：
- 我们使用hash表，hash表中存储（字符串数组元素排序结果 - 结果数组元素）
- 我们遍历字符串数组，先将该元素排序，排序后，如果hash表中有这个关键字，那么就添加这个字符串数组元素进value
- 如果没有，就先申请空间，再添加
- 最后将hash表中的value全部返回即可。
解题代码：
//时间复杂度：O(NlogN)
//空间复杂度：O(n)
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> hash = new HashMap<>();
for(int i = 0; i < strs.length; i++) {
//字符串数组元素排序
char[] tmp = strs[i].toCharArray();
Arrays.sort(tmp);
String key = new String(tmp);
if(!hash.containsKey(key)) {
hash.put(key, new ArrayList());
}
hash.get(key).add(strs[i]);
}
return new ArrayList(hash.values());
}
}