涉及题目：1.两数之和、49.字母异位词分组、128.最长连续序列
核心思想：哈希表依靠平均 O(1) 的查找特性，用空间换取时间，消除暴力双层循环

基础概念区分

Java 中两类常用哈希容器：

• HashSet：只存储元素，适合判断元素是否存在、去重
• HashMap：存储键值对映射，适合记录附属信息、归类分组

1. 两数之和｜LeetCode 1

题意

给定数组与目标值 target，找到相加等于 target 的两个数字下标，同一个元素不能重复使用。

解题思路

暴力双层循环时间复杂度 $O(n^2)$，效率很低。
哈希优化思路：遍历数组时，对当前数字 nums[i]，我们需要寻找互补值 need = target - nums[i]。

1. 先查询哈希表中是否存在互补值 need
   • 存在：直接返回两个下标
   • 不存在：把当前数字和下标存入哈希表

重点：先判断、后存入，避免同一个元素和自身匹配出错（例如输入 [3,3]，target=6）

Java 代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int need = target - nums[i];
            if(hash.containsKey(need)){
                return new int[]{hash.get(need), i};
            }
            hash.put(nums[i],i);
        }
        return new int[0];
    }
}

复杂度

时间：$O(n)$，数组仅遍历一次
空间：$O(n)$，哈希表最多存储全部数组元素

考点总结

HashMap 构建「数值→下标」映射；经典寻找互补数模型。

2. 字母异位词分组｜LeetCode 49

题意

字母异位词指字符组成完全一致、顺序不同的字符串，要求将所有异位词分到同一组。

解题思路

核心性质：互为异位词的字符串，排序之后得到的字符串完全相同。
利用该特性做哈希分组：

1. 逐个遍历字符串
2. 将字符串转为字符数组排序，生成统一标识 key
3. HashMap 的 key 存放排序后的标准字符串，value 存放同一组异位词列表
4. 遍历完成后，取出 map 内所有列表作为最终结果

Java 代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> hash = new HashMap<>();
        for(String str : strs){
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = hash.getOrDefault(key,new ArrayList<>());
            list.add(str);
            hash.put(key,list);
        }
        return new ArrayList<>(hash.values());
    }
}

复杂度

时间：$O(nk\log k)$，n为字符串数量，k为单个字符串最大长度，排序耗时 $k\log k$
空间：$O(nk)$，存储全部字符串

考点总结

哈希分组模型；核心是构造统一哈希键，把同类元素聚合在一起。
拓展优化：可以不用排序，统计26个字母出现次数拼接字符串作为key，消除排序开销。

3. 最长连续序列｜LeetCode 128

题意

无序整数数组，找出数字连续的最长序列长度，题目要求最优时间复杂度 $O(n)$。

解题思路

直接排序解法复杂度 $O(n\log n)$，达不到最优标准，使用 HashSet 实现：

1. 将全部数字存入 HashSet，实现O(1)存在性查询
2. 遍历集合内每一个数字 num
   • 关键剪枝：如果集合中存在 num - 1，说明当前数字不是一段连续序列的起点，直接跳过
   • 只有 !set.contains(num - 1) 时，num 才是序列起点
   • 从起点向后持续查找 num+1、num+2……统计序列长度
3. 不断更新全局最长序列长度

复杂度说明：每个数字只会被while循环访问一次，整体复杂度保证 $O(n)$，不存在重复遍历。

Java 代码

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

复杂度

时间：$O(n)$
空间：$O(n)$

考点总结

HashSet 快速判断元素存在；利用条件剪枝避免重复遍历；识别连续序列起点。

哈希表三类解题模型归纳

1. 两数之和（HashMap）：寻找互补元素，建立数值与附属信息的映射
2. 字母异位词分组（HashMap）：构造统一key，实现同类元素分组归集
3. 最长连续序列（HashSet）：专注元素存在性查询，搭配逻辑剪枝优化性能

通用解题思路

1. 遇到需要快速查找、匹配、去重、分组的场景，优先考虑哈希表
2. 只需要判断元素有无 → HashSet；需要保存额外信息（下标、分组）→ HashMap
3. 时刻留意重复遍历问题，增加条件判断做剪枝，防止时间复杂度恶化

面试思考拓展

1. 两数之和能否先全部put进map再遍历？容易出现自身匹配错误，标准写法必须先查询再存入
2. 最长连续序列排序解法与哈希解法的优缺点对比
3. 字母异位词排序法存在性能瓶颈，如何使用字母计数法进行优化

如果你想要，我可以把这份笔记精简成适合直接复制到文档的纯文本版本。