力扣 Hot100 系统复习（二）：哈希

本文根据学习仓库 2-哈希 的三篇 Markdown 整理，保留题目、核心思路与 Java 实现。完整题单见专栏目录。

1. 两数之和

题目： 给定整数数组 nums 和目标值 target，返回和为目标值的两个元素下标，不能重复使用同一个元素。

输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]

暴力枚举所有配对需要 O(n²)。用哈希表记录“数值 → 下标”，遍历当前数字时，查找补数 target - nums[i]：

补数存在，直接返回两个下标。
补数不存在，记录当前数字及下标。
先查找，再存入，避免当前元素与自己配对。

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[]{};
}

平均时间复杂度 O(n)，额外空间复杂度 O(n)。

2. 字母异位词分组

题目： 将字符种类和出现次数相同、排列顺序可以不同的字符串分到同一组。

输入：["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

排序法： 把每个字符串的字符排序，得到统一的键。例如 eat、tea、ate 排序后都是 aet。用哈希表保存“排序后的字符串 → 原字符串列表”。

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();

    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);

        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(str);
    }

    return new ArrayList<>(map.values());
}

设字符串数量为 n，最长字符串长度为 k。排序法通常记为平均时间 O(nk log k)，额外空间上界为 O(n(k + 1))，包括分组键与列表引用。

计数法： 原文还提供了另一种实现：统计 26 个小写字母的出现次数，将计数用 # 分隔后拼成键，再按键分组。这样无需排序，平均时间为 O(n(k + 26))。分隔符用于避免 [1, 11] 与 [11, 1] 都被拼成 111。

3. 最长连续序列

题目： 给定未排序整数数组，求数值连续的最长序列长度，元素不要求在原数组中相邻。

输入：[100, 4, 200, 1, 3, 2]
最长连续序列：[1, 2, 3, 4]
输出：4

排序后扫描需要 O(n log n)，不满足题目要求的线性时间。哈希集合的做法是：

将所有数字存入 HashSet，便于查找并去重。
对每个数字 num，只有 num - 1 不存在时，才从它开始查找。
不断查找后继数字，更新最长长度。

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }

    int maxLength = 0;
    for (int num : set) {
        if (!set.contains(num - 1)) {
            int currentNum = num;
            int currentLength = 1;

            while (set.contains(currentNum + 1)) {
                currentNum++;
                currentLength++;
            }

            maxLength = Math.max(maxLength, currentLength);
        }
    }

    return maxLength;
}