哈希表

1 两数之和

【原始题目】

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]。

示例 2：

输入：nums = [3,2,4], target = 6 输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6 输出：[0,1]

提示：

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 只会存在一个有效答案

进阶： 你可以想出一个时间复杂度小于 $O(n^2)$ 的算法吗？

【题目速记】

• 给一个数组和一个目标值。
• 找两个不同下标的元素，和为 target。
• 返回这两个下标，顺序随意。
• 只有一个答案，同一元素不能用两次。
• 进阶要求：比 $O(n^2)$ 更快。

【题解】

一句话速通：两层循环暴力枚举所有数对，找到和等于 target 的一对即返回下标。

【算法思想】

• 暴力枚举，双重循环
• 外循环固定左边元素，内循环扫描右边剩余元素
• 检查两者之和是否等于目标值

【核心思路】

1. 外层循环 i 从 0 走到 n-1。
2. 内层循环 j 从 i+1 走到 n-1。
3. 若 nums[i] + nums[j] == target，直接返回 new int[]{i, j}。

【复杂度】

• 时间复杂度 $O(n^2)$ ：两层循环，每层最坏遍历 $n$ 个元素。
• 空间复杂度 $O(1)$ ：只用了常数个变量。

【伪代码】

for i = 0 to n-1:
    for j = i+1 to n-1:
        if nums[i] + nums[j] == target:
            return [i, j]

【易错点】

• 内层循环从 i+1 开始，避免使用相同元素或重复组合。
• 返回的是下标，不是数值。

【完整代码】

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0]; // 题目保证一定有解，不会走到这
    }
}

【题解】

一句话速通：用哈希表存储已遍历元素的值与下标，每到一个新数，直接查表找 target - nums[i]，实现一次遍历 $O(n)$ 。

【算法思想】

• 哈希表（HashMap），以空间换时间
• 存储“值 → 下标”的映射
• 一次遍历，边查边存

【核心思路】

1. 创建一个哈希表 map。
2. 遍历数组下标 i，对于每个数 x = nums[i]：
   • 计算 complement = target - x。
   • 若 complement 在 map 中存在，则返回 [map.get(complement), i]。
   • 否则将 (x, i) 存入 map。
3. 题目保证有解，循环内必定返回。

【复杂度】

• 时间复杂度 $O(n)$ ：只遍历数组一次，哈希表插入和查找为 $O(1)$。
• 空间复杂度 $O(n)$ ：最坏情况下哈希表存储所有元素。

【伪代码】

map = 空哈希表
for i = 0 to n-1:
    complement = target - nums[i]
    if map 包含 complement:
        return [map.get(complement), i]
    map.put(nums[i], i)

【易错点】

• 先检查哈希表，再插入当前元素，避免同一个元素用两次（如 target = 6, nums = [3, ...]，不会把 3 和自己配对）。
• 返回顺序可以任意，[map.get(complement), i] 是合法的。
• 题目数据范围包含负数，哈希表方法仍适用。

【完整代码】

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

2 字母异位词分组

【原始题目】

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:
输入: strs = [""]
输出: [[""]]

示例 3:
输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

【题目速记】

给一堆字符串，把“相同字符组成、不同排列”的互为异位词的字符串分到同一组，最后返回所有分组。字符串只含小写字母。

【题解】

一句话速通：对每个字符串排序，用排序后的统一形式作为哈希表的键，把原字符串归到对应分组。

【算法思想】

• 哈希表 + 排序
• 哈希表：用来按“字符排序后字符串”分组
• 排序：把每个字符串的字符排成固定顺序，让异位词映射到同一个键

【核心思路】

1. 遍历 strs，每拿到一个字符串，把它转为字符数组并排序，得到统一键
2. 用 HashMap<String, List<String>>，键是排序后的串，值是原字符串列表
3. 最后把 map 里所有的值收集起来返回

【复杂度】

• 时间复杂度 $O(n \cdot k \log k)$ ： $n$ 是字符串个数， $k$ 是最长字符串长度，每个字符串都要排序
• 空间复杂度 $O(n \cdot k)$ ：需要存储所有字符串到哈希表中

【伪代码】

创建 HashMap<String, List<String>> map
for 每个 s 在 strs 中:
    key = 将 s 转为 char[] 后排序，再转回 String
    若 map 中没有 key，新建一个空列表
    map.get(key).add(s)
返回 new ArrayList<>(map.values())

【易错点】

• 排序必须把 char[] 转回 String，不能直接用 char[] 当键（数组的 equals 比较的是引用）
• 空字符串排序后仍是空串，可以直接当键，不需要特判
• 返回类型是 List<List<String>>，要用 new ArrayList<>(map.values()) 包装一下

【完整代码】

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

【题解】

一句话速通：用长度为 26 的计数数组统计每个字符出现次数，将计数编码成字符串作为键，哈希表完成分组。

【算法思想】

• 哈希表 + 字符计数
• 字符计数：统计每个小写字母的出现次数，生成异位词的唯一指纹
• 哈希表：把相同指纹的字符串归为一组

【核心思路】

1. 遍历每个字符串，用一个 int[26] 记录 'a'~'z' 的出现次数
2. 把计数数组编码成带分隔符的字符串（例如 #2#1#0...），作为键
3. 用 HashMap 把原字符串塞进对应键的分组，最后返回所有分组列表

【复杂度】

• 时间复杂度 $O(n \cdot (k + 26))$ ： $n$ 是字符串个数， $k$ 是平均长度，每个字符串要计数并构建固定 26 位的键
• 空间复杂度 $O(n \cdot k)$ ：存储所有字符串及键

【伪代码】

创建 HashMap<String, List<String>> map
for 每个 s 在 strs 中:
    count = new int[26]
    for 每个字符 c 在 s 中:
        count[c - 'a']++
    用 StringBuilder 拼接 '#' 和每个 count[i] 得到 key
    map.computeIfAbsent(key, k -> new ArrayList).add(s)
返回 new ArrayList<>(map.values())

【易错点】

• 计数拼接时 必须加分隔符，直接拼数字可能在极端情况下造成不同计数产生相同字符串（如 "aab" 和 "abb" 不会撞，但规范写法更安全）
• int[] 不能直接当键，一定要编码成 String
• 26 个字母固定循环，不要写成动态长度，否则失去分组唯一性

【完整代码】

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

3 最长连续序列

【原始题目】

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。

示例 1： 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2： 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9

示例 3： 输入：nums = [1,0,1,2] 输出：3

提示：

• $0 \le nums.length \le 10^5$
• $-10^9 \le nums[i] \le 10^9$

【题目速记】

未排序数组，找出能组成连续数字的最长长度，元素顺序无所谓，但数字必须连续（如 1,2,3）。要求时间 $O(n)$ 。

【题解】

一句话速通：用 HashSet 去重并实现 $O(1)$ 查找，只从连续序列的起点向后扩展，保证每个数字仅被访问常数次，整体 $O(n)$。

【算法思想】

• 哈希表：HashSet 存储所有数字，用于快速判断某个数字是否存在。
• 贪心剪枝：只从连续序列的“起点”（即 $num-1$ 不在集合中）开始统计长度，避免重复计数。

【核心思路】

1. 将所有数字存入 HashSet，自动去重。
2. 遍历集合中的每个数字 num。
3. 若 num-1 不在集合中，说明 num 是一个连续序列的起点。
4. 从 num 出发，不断检查 num+1、num+2… 是否存在，统计当前序列长度并更新最大长度。
5. 所有非起点的数字会被跳过，保证每个数字最多被访问两次，总复杂度 $O(n)$。

【复杂度】

• 时间复杂度 $O(n)$ ：每个数字只作为起点检查一次，在扩展时被访问一次，整体线性遍历。
• 空间复杂度 $O(n)$ ：哈希集合存储所有元素。

【伪代码】

function longestConsecutive(nums):
    将 nums 所有元素放入 set
    longest = 0
    for each num in set:
        if num-1 不在 set 中:          // 是连续序列的起点
            currentNum = num
            currentStreak = 1
            while currentNum+1 在 set 中:
                currentNum++
                currentStreak++
            longest = max(longest, currentStreak)
    return longest

【易错点】

• 必须跳过 $num-1$ 存在的元素，否则每个数字都会触发 while 循环，退化为 $O(n^2)$。
• 遍历时要遍历 set 而非原数组，避免重复元素干扰。
• 空数组直接返回 0。

【完整代码】

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int longest = 0;
        for (int num : set) {
            // 只有当 num 是序列起点时才统计
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                longest = Math.max(longest, currentStreak);
            }
        }
        return longest;
    }
}

【题解】

一句话速通：先排序，再遍历统计连续递增长度，跳过重复数字，时间 $O(n \log n)$ ，但不符合题目的 $O(n)$ 要求，可作为备选答案展示。

【算法思想】

• 排序：将数组变为有序，使连续数字在位置上相邻。
• 遍历比较：维护当前连续长度，遇到相等跳过，遇到差 1 增加长度，否则重置。

【核心思路】

1. 对 nums 排序。
2. 初始化 longest = 1，currentStreak = 1。
3. 从下标 1 开始遍历：
   • 若 nums[i] == nums[i-1]：跳过重复。
   • 若 nums[i] == nums[i-1] + 1：currentStreak++。
   • 否则：更新 longest，重置 currentStreak = 1。
4. 最后返回 max(longest, currentStreak)。

【复杂度】

• 时间复杂度 $O(n \log n)$ ：排序主导。
• 空间复杂度 $O(1)$ （忽略排序栈，可视为原地）。

【伪代码】

function longestConsecutive(nums):
    if nums 为空: return 0
    排序 nums
    longest = 1
    currentStreak = 1
    for i from 1 to n-1:
        if nums[i] == nums[i-1]: continue
        if nums[i] == nums[i-1] + 1:
            currentStreak++
        else:
            longest = max(longest, currentStreak)
            currentStreak = 1
    return max(longest, currentStreak)

【易错点】

• 必须跳过重复元素，否则重复会错误地重置计数或错误递增。
• 循环结束后需要再次比较 longest 和 currentStreak，防止最长序列在末尾。

【完整代码】

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Arrays.sort(nums);
        int longest = 1;
        int currentStreak = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                continue;   // 跳过重复
            }
            if (nums[i] == nums[i-1] + 1) {
                currentStreak++;
            } else {
                longest = Math.max(longest, currentStreak);
                currentStreak = 1;
            }
        }
        return Math.max(longest, currentStreak);
    }
}