当前位置：首页 > ai >正文

力扣hot100:字母异位词分组和最长连续序列（49，128）

ai 2025/8/28 20:56:26

今天回顾一下力扣hot100中两道Hash的题。下面分享我的思路和代码实现。

问题描述

核心思路

字母异位词的本质是字符组成相同但顺序不同。因此，如果我们将每个字符串的字符排序，所有异位词都会得到相同的排序后字符串。利用这一特性：

将每个字符串排序后的结果作为哈希表的键
原始字符串作为值存入对应键的列表中
最终哈希表的所有值就是分组结果

代码实现

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String,List<String>> map=new HashMap<>();for (String str : strs) {char[] charArray = str.toCharArray();Arrays.sort(charArray);String temp_str=new String(charArray);List<String> orDefault = map.getOrDefault(temp_str, new ArrayList<>());orDefault.add(str);map.put(temp_str,orDefault);}List<List<String>> result=new ArrayList<>(map.values());return result;}
}

关键点解析

排序归一化：通过 Arrays.sort(charArray) 将异位词统一为相同的字符串形式
哈希表映射：使用 HashMap 将排序后字符串映射到原始字符串列表
高效操作：
- getOrDefault() 确保键不存在时自动创建新列表
- 直接操作列表引用避免多余对象创建
简洁返回：new ArrayList<>(map.values()) 一键转换结果格式

复杂度分析

时间复杂度：O(nklogk) （n 是字符串数量，k 是字符串最大长度，排序每个字符串耗时 klogk）
空间复杂度：O(nk) （哈希表存储所有字符串）

其他优化思路

计数法：用长度26的数组统计字符频率，将频率数组转为字符串作为键（时间复杂度 O(nk)）
质数乘积法：为每个字母分配质数，用乘积作为键（需处理大数溢出问题）

LeetCode 128：最长连续序列的巧妙解法——哈希表高效策略

解题思路

核心问题在于如何避免排序（排序时间复杂度为 O(n log n)）并实现 O(n) 的时间复杂度。我们可以利用 哈希表 的 O(1) 查询特性：

去重存储：先将所有数字存入 HashSet 中，去除重复元素。
定位序列起点：遍历哈希表，若当前数字 i 的前驱 i-1 不存在，则 i 可作为连续序列的起点。
扩展序列：从起点 i 开始，向后查找 i+1, i+2, ... 是否在哈希表中，统计序列长度。
更新最大值：比较并更新最长序列长度。

关键优化：通过检查 i-1 跳过非起点元素，确保每个连续序列只被遍历一次，实现 O(n) 时间复杂度。

代码实现

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set=new HashSet<>();for (int num : nums) {set.add(num);}int max=0;for(int i:set){int temp=1;if(set.contains(i-1)){continue;}else{int temp_num=i;while(set.contains(temp_num+1)){temp++;temp_num++;}max=Math.max(max,temp);}}return max;}}

代码解析

去重存储：
- 使用 HashSet 存储数组元素，自动去重。
遍历起点：
- 遍历哈希表，若 i-1 存在于集合中，说明 i 不是序列起点，直接跳过。
- 核心逻辑：每个连续序列只会被起点触发一次。
扩展序列：
- 从起点 i 开始，向后循环查找连续数字 i+1, i+2...
- 每找到一个连续数字，当前序列长度 currLen 加 1。
更新结果：
- 每次完成序列扩展后，更新全局最大值 maxLen。