Leetcode Hot100 哈希
1. 两数之和 - 力扣（LeetCode）¶
class Solution {
//使用哈希表
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
// 如果数组为空则直接退出
if(nums == null || nums.length == 0){
return res;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int temp = target - nums[i]; // 遍历当前元素，并在map中寻找是否有匹配的key
if(map.containsKey(temp)){
res[1] = i;
res[0] = map.get(temp);// 这里就是满足了匹配下，从map中获取到对应的下标，于是可以被res返回
break;
}
map.put(nums[i], i); // 如果没找到匹配对，就把访问过的元素和下标加入到map中
// 因为后面查询到的元素会回头向前匹配，这样就避免了使用两次for循环的暴力解法
}
// 之所以要用（数组值，数组下标）这样的结构以及map来实现，是因为最终要返回的不是所求得的值，而是值在数组中所对应的下标
return res;
}
}
**复杂度分析：**
- **时间复杂度：O(n)**，其中 n 是数组的长度。遍历数组一次，哈希表的查找和插入操作都是 O(1) 时间复杂度。
- **空间复杂度：O(n)**，其中 n 是数组的长度。哈希表最多存储 n 个键值对。
class Solution {
//使用哈希表方法2
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> indexMap = new HashMap<>();
// 本质上也是减少了“从后往前”的二次查询的复杂度
// 因为暴力解法之所以麻烦的原因是因为，代码不清楚之前所访问过的元素是否满足和当前元素搭配的情况
// 所以才需要每个元素都重复访问一次全组
// 而HashMap的优化就免去了冗余的重复访问，直接将访问过的元素存入map，等到后面查询的时候直接查询map即可
for(int i = 0; i < nums.length; i++){
int balance = target - nums[i]; // 记录当前的目标值的余数
if(indexMap.containsKey(balance)){ // 查找当前的map中是否有满足要求的值
return new int []{i, indexMap.get(balance)}; // 如果有，返回目标值
} else{
indexMap.put(nums[i], i); // 如果没有，把访问过的元素和下标加入map中
}
}
return null;
}
}
**复杂度分析：**
- **时间复杂度：O(n)**，其中 n 是数组的长度。遍历数组一次，哈希表的查找和插入操作都是 O(1) 时间复杂度。
- **空间复杂度：O(n)**，其中 n 是数组的长度。哈希表最多存储 n 个键值对。
49. 字母异位词分组 - 力扣（LeetCode）¶
class Solution {
// 设计思路，通过hashmap比较不同单词是否以一个顺序的同一单词变换而来
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String,ArrayList<String>> map = new HashMap<>();// 重点1：懂得使用java的hashmap来存储数据
// 重点2：hashmap的类型应该为以string为键，返回的数组为值
for(String s: strs){
char[] chars = s.toCharArray();// 重点3：toCharArray方法
Arrays.sort(chars);
String key = Arrays.toString(chars);
if(!map.containsKey(key)){
map.put(key,new ArrayList<String>());
}
map.get(key).add(s);
}
return new ArrayList<>(map.values());// 重点4：将map的values转为数组的方法
}
}
**复杂度分析：**
- **时间复杂度：O(nk log k)**，其中 n 是字符串数组的长度，k 是字符串的最大长度。每个字符串需要排序，排序的时间复杂度是 O(k log k)，总共有 n 个字符串。
- **空间复杂度：O(nk)**，其中 n 是字符串数组的长度，k 是字符串的最大长度。需要存储所有字符串到哈希表中。
提升
// 遍历数组: 拿出每一个字符串
// 寻找"代表元"(制造Key): 将字符串拆成字符, 按字母顺序排序, 然后再拼回字符串. 比如 "tea" 和 "eat" 排序后都会变成 "aet".
// 哈希分组(放入字典): 把这个排序后的字符串 "aet" 当作 Key，把原始字符串存入对应的 List (Value) 中
// 提取结果: 最后把哈希表里所有的 List 提取出来, 组合成一个大的 List 返回.
import java.util.*;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
return new AbstractList<List<String>>() {
List<List<String>> list;
private void init() {
if (list != null) return;
Map<String, List<String>> m = new HashMap<>();
for (String s : strs) {
String sorted = sort(s);
List<String> group = m.get(sorted);
if (group != null) {
group.add(s);
} else {
List<String> newGroup = new ArrayList<>();
newGroup.add(s);
m.put(sorted, newGroup);
}
}
list = new ArrayList<>(m.values());
}
private String sort(String s) {
char[] S = s.toCharArray();
Arrays.sort(S);
return new String(S);
}
@Override
public int size() {
init();
return list.size();
}
@Override
public List<String> get(int i) {
init();
return list.get(i);
}
};
}
}
**复杂度分析：**
- **时间复杂度：O(nk log k)**，其中 n 是字符串数组的长度，k 是字符串的最大长度。每个字符串需要排序，排序的时间复杂度是 O(k log k)，总共有 n 个字符串。
- **空间复杂度：O(nk)**，其中 n 是字符串数组的长度，k 是字符串的最大长度。需要存储所有字符串到哈希表中。
- **注**：该方法使用了懒加载的方式，只有在首次访问时才会计算结果，节省了不必要的计算时间。
128. 最长连续序列 - 力扣（LeetCode）¶
class Solution {
public int longestConsecutive(int[] nums) {
// 先对数据按从小到大排序，再顺序比较数组内的每个数之间是否连续
// 如果连续，就记录下当前的连续序列的长度
// 如果不连续，就更新最大连续序列的长度
// 最后返回最大连续序列的长度
if (nums == null || nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int maxLength = 1;
int currentLength = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
continue;
}
if (nums[i] == nums[i - 1] + 1) {
currentLength++;
} else {
maxLength = Math.max(maxLength, currentLength);
currentLength = 1;
}
}
maxLength = Math.max(maxLength, currentLength);
return maxLength;
}
}
**复杂度分析：**
- **时间复杂度：O(n log n)**，其中 n 是数组的长度。排序的时间复杂度是 O(n log n)，遍历数组的时间复杂度是 O(n)，因此总时间复杂度是 O(n log n)。
- **空间复杂度：O(1)**，只使用了常数级别的额外空间。
哈希表解题方法**
class Solution {
public int longestConsecutive(int[] nums) {
// 创建哈希集合，用于存储数组中的所有元素，实现O(1)时间的查找
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
// 记录最长连续序列的长度
int longestStreak = 0;
// 遍历哈希集合中的每个元素
for (int num : num_set) {
// 关键优化：只有当num-1不存在时，才以num为起点开始计算连续序列
// 这样可以避免重复计算，确保每个连续序列只被计算一次
if (!num_set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
// 从当前起点开始，向后查找连续的数字
while (num_set.contains(currentNum + 1)) {
// 假设当前数字的下一个数字存在，就继续查找连续序列的下一个数字
currentNum += 1; // 当前数字增加1，继续查找连续序列
currentStreak += 1; // 当前连续序列的长度增加1
}
// 更新最长连续序列的长度
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
**复杂度分析：**
- **时间复杂度：O(n)**，其中 n 是数组的长度。每个元素最多被访问两次，一次是添加到哈希集合中，一次是在查找连续序列时。
- **空间复杂度：O(n)**，其中 n 是数组的长度。哈希集合需要存储所有元素。