哈希算法练习

哈希表（Hash Table）利用哈希函数将键（Key）映射到桶（Bucket）中，从而实现 O(1) 的平均查找时间。它是解决查找、频率统计和去重问题的常用利器。

哈希表的核心思想是用空间换时间。通过额外的存储空间，我们将查找操作从 O(n) 降低到 O(1)。在算法面试中，当你发现需要频繁查找某个元素是否存在，或者需要统计元素出现次数时，哈希表往往是首选方案。

1. 两数之和 (Two Sum)

题目描述

给定一个整数数组 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) 的算法吗？

解题思路

这道题的核心问题是：对于数组中的每个元素 nums[i]，我们需要找到另一个元素 nums[j]，使得 nums[i] + nums[j] = target。换句话说，我们需要查找 target - nums[i] 是否存在于数组中。

方法一：暴力枚举

最直观的方法是使用两层循环，遍历所有可能的数对。外层循环选取第一个数，内层循环选取第二个数，检查它们的和是否等于 target。

这种方法虽然简单，但时间复杂度为 O(n²)，当数组长度达到 10^4 时，总运算次数可能达到 10^8 级别，在时间限制内难以通过。

方法二：哈希表

暴力方法的瓶颈在于查找操作：对于每个元素，我们需要 O(n) 的时间来查找配对元素。哈希表可以将查找时间降低到 O(1)。

具体做法是遍历数组，对于每个元素 nums[i]，计算它的配对值 complement = target - nums[i]。如果 complement 已经在哈希表中，说明我们找到了答案；如果不在，就将当前元素及其下标存入哈希表，继续遍历。

这里有一个关键点：为什么我们可以在一遍遍历中完成？因为我们只需要找到一对答案，而且题目保证答案存在。当我们遍历到答案的第二个元素时，第一个元素一定已经在哈希表中了。

图解示例

以 nums = [3, 2, 4], target = 6 为例：

初始状态：哈希表为空 {}

第1次遍历 i=0, nums[0]=3:
  complement = 6 - 3 = 3
  3 不在哈希表中
  将 {3: 0} 存入哈希表
  哈希表: {3: 0}

第2次遍历 i=1, nums[1]=2:
  complement = 6 - 2 = 4
  4 不在哈希表中
  将 {2: 1} 存入哈希表
  哈希表: {3: 0, 2: 1}

第3次遍历 i=2, nums[2]=4:
  complement = 6 - 4 = 2
  2 在哈希表中！对应的下标是 1
  返回 [1, 2]

Java 代码实现

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 创建哈希表，键为数值，值为下标
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            // 计算配对值：我们需要找一个数，使得它加上当前数等于 target
            int complement = target - nums[i];
            
            // 检查配对值是否已存在于哈希表中
            if (map.containsKey(complement)) {
                // 找到答案，返回两个数的下标
                return new int[]{map.get(complement), i};
            }
            
            // 将当前数存入哈希表，供后续查找使用
            map.put(nums[i], i);
        }
        
        // 根据题目保证，一定会找到答案，这行代码不会执行
        return new int[]{-1, -1};
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组长度。我们只遍历数组一次，每次查找和插入哈希表的操作都是 O(1)。

空间复杂度：O(n)，最坏情况下需要将 n-1 个元素存入哈希表。

易错点

存入哈希表的时机：必须先查找再存入。如果先存入当前元素再查找，当 target = 2 * nums[i] 时，会错误地返回同一个下标两次。
相同元素的处理：题目保证答案唯一，但数组中可能有重复元素。例如 [3, 3]，当遍历到第二个 3 时，第一个 3 已经在哈希表中，可以正确找到答案。

49. 字母异位词分组 (Group Anagrams)

题目描述

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

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 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] 仅包含小写字母

解题思路

这道题的核心问题是：如何判断两个字符串互为字母异位词？

字母异位词的特点是：两个字符串包含完全相同的字母，只是顺序不同。由此我们可以得出两种判断方法：

方法一：排序法

如果两个字符串互为字母异位词，那么它们排序后的结果一定相同。例如 "eat" 和 "tea" 排序后都是 "aet"。

我们可以遍历字符串数组，对每个字符串排序后作为哈希表的键，将原始字符串加入到对应键的列表中。

方法二：计数法

由于字符串只包含小写字母，我们可以用一个长度为 26 的数组统计每个字母的出现次数，然后将这个计数数组转换为字符串作为键。

例如 "abb" 的计数为 [1,2,0,0,...]，可以编码为 "a1b2" 或 "1#2#0#0#..."。

两种方法的比较：

方法	时间复杂度	适用场景
排序法	O(n × k log k)	通用，代码简洁
计数法	O(n × k)	字符集有限时更优

其中 n 是字符串数量，k 是字符串的平均长度。

图解示例

以 strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 为例：

遍历过程（排序法）：

"eat" → 排序后 "aet" → 分组 {aet: [eat]}
"tea" → 排序后 "aet" → 分组 {aet: [eat, tea]}
"tan" → 排序后 "ant" → 分组 {aet: [eat, tea], ant: [tan]}
"ate" → 排序后 "aet" → 分组 {aet: [eat, tea, ate], ant: [tan]}
"nat" → 排序后 "ant" → 分组 {aet: [eat, tea, ate], ant: [tan, nat]}
"bat" → 排序后 "abt" → 分组 {aet: [eat, tea, ate], ant: [tan, nat], abt: [bat]}

最终结果：[[eat, tea, ate], [tan, nat], [bat]]

Java 代码实现

方法一：排序法

class Solution {
    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);
            
            // 如果键不存在则创建新列表，存在则获取已有列表
            // computeIfAbsent：如果 key 不存在，用 lambda 创建新列表
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        
        // 返回所有分组
        return new ArrayList<>(map.values());
    }
}

方法二：计数法

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String str : strs) {
            // 统计每个字母的出现次数
            int[] count = new int[26];
            for (char c : str.toCharArray()) {
                count[c - 'a']++;
            }
            
            // 将计数数组转换为字符串作为键
            // 例如 [1,2,0,...] 转换为 "a1b2c0..."
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append((char) ('a' + i));
                sb.append(count[i]);
            }
            String key = sb.toString();
            
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        
        return new ArrayList<>(map.values());
    }
}

复杂度分析

排序法：

时间复杂度：O(n × k log k)，其中 n 是字符串数量，k 是字符串的平均长度
空间复杂度：O(n × k)，需要存储所有字符串

计数法：

时间复杂度：O(n × k)，遍历每个字符串的每个字符
空间复杂度：O(n × k)，同上

易错点

空字符串的处理：空字符串排序后还是空字符串，单独成一组。
键的设计：计数法中，键必须能唯一标识字母组成。简单的做法是将每个字母及其计数拼接，如 "a1b2"，避免歧义。
computeIfAbsent 的使用：这个方法可以简化代码，避免先检查键是否存在再操作的繁琐逻辑。

128. 最长连续序列 (Longest Consecutive Sequence)

题目描述

给定一个未排序的整数数组 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
解释：最长数字连续序列是 [0, 1, 2, 3, 4, 5, 6, 7, 8]。它的长度为 9。

示例 3：

输入：nums = []
输出：0

约束条件：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

解题思路

这道题要求 O(n) 时间复杂度，这意味着我们不能使用排序（O(n log n)）。关键在于如何避免重复计算。

方法一：排序法（非最优）

先对数组排序，然后遍历找最长连续序列。时间复杂度 O(n log n)，不满足题目要求。

方法二：哈希集合（最优）

核心思想：只从序列的起点开始计数，避免重复计算。

一个数 num 是某个连续序列的起点，当且仅当 num - 1 不在数组中。例如在 [1, 2, 3, 10, 11, 12] 中，只有 1 和 10 是序列起点。

算法步骤：

将所有数字存入哈希集合，实现 O(1) 查找
遍历集合中的每个数字 num
如果 num - 1 不在集合中，说明 num 是序列起点
从起点开始，不断检查 num + 1, num + 2, ... 是否在集合中，统计序列长度
更新最长序列长度

这种方法保证每个数字最多被访问两次：一次作为序列中的元素，一次检查它是否是起点。因此总时间复杂度为 O(n)。

图解示例

以 nums = [100, 4, 200, 1, 3, 2] 为例：

第一步：构建哈希集合
Set = {100, 4, 200, 1, 3, 2}

第二步：遍历并寻找序列起点

检查 100：
  99 不在 Set 中 → 100 是起点
  向后查找：101 不在 Set 中 → 序列长度 = 1
  
检查 4：
  3 在 Set 中 → 4 不是起点，跳过
  
检查 200：
  199 不在 Set 中 → 200 是起点
  向后查找：201 不在 Set 中 → 序列长度 = 1
  
检查 1：
  0 不在 Set 中 → 1 是起点
  向后查找：2 在 Set 中，3 在 Set 中，4 在 Set 中，5 不在 Set 中
  序列长度 = 4（1, 2, 3, 4）→ 更新最大长度
  
检查 3：
  2 在 Set 中 → 3 不是起点，跳过
  
检查 2：
  1 在 Set 中 → 2 不是起点，跳过

最终结果：4

Java 代码实现

class Solution {
    public int longestConsecutive(int[] nums) {
        // 处理空数组的边界情况
        if (nums.length == 0) {
            return 0;
        }
        
        // 将所有数字存入哈希集合，实现 O(1) 查找
        // 使用 Set 而非 List，自动去重
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        
        int maxLen = 0;
        
        // 遍历集合中的每个数字
        for (int num : set) {
            // 关键优化：只从序列起点开始计数
            // 如果 num-1 存在，说明 num 不是起点，跳过
            if (!set.contains(num - 1)) {
                // num 是序列起点，开始统计长度
                int currNum = num;
                int currLen = 1;
                
                // 不断检查下一个连续数字是否存在
                while (set.contains(currNum + 1)) {
                    currNum++;
                    currLen++;
                }
                
                // 更新最长序列长度
                maxLen = Math.max(maxLen, currLen);
            }
        }
        
        return maxLen;
    }
}

复杂度分析

时间复杂度：O(n)

虽然有两层循环，但内层 while 循环只对每个序列的起点执行。每个数字在整个算法过程中最多被访问两次：

一次检查它是否是序列起点
一次作为某个序列的成员被遍历

因此总时间复杂度为 O(n)。

空间复杂度：O(n)

需要哈希集合存储所有数字。

正确性证明

为什么这个算法是 O(n)？

关键在于：对于任意数字 num，它只会在两种情况下被访问：

作为序列起点（num - 1 不存在）：此时会遍历整个序列
作为序列成员：在某个起点开始的遍历中被访问

每个数字最多作为成员被访问一次，所以总访问次数是 O(n)。

易错点

遍历集合而非原数组：如果遍历原数组而非集合，当存在重复元素时会造成重复计算。
起点的判断条件：必须是 num - 1 不存在，而不是 num + 1 不存在。后者会导致只找到序列终点，而非完整序列。
空数组的处理：题目允许空数组，此时应返回 0。
使用 HashSet 而非 HashMap：这道题只需要判断元素是否存在，不需要存储额外信息，Set 更合适。

哈希算法练习

1. 两数之和 (Two Sum)

题目描述

解题思路

方法一：暴力枚举

方法二：哈希表

图解示例

Java 代码实现

复杂度分析

易错点

相关题目

49. 字母异位词分组 (Group Anagrams)

题目描述

解题思路

方法一：排序法

方法二：计数法

图解示例

Java 代码实现

复杂度分析

易错点

相关题目

128. 最长连续序列 (Longest Consecutive Sequence)

题目描述

解题思路

方法一：排序法（非最优）

方法二：哈希集合（最优）

图解示例

Java 代码实现

复杂度分析

正确性证明

易错点

相关题目

1. 两数之和 (Two Sum)​

题目描述​

解题思路​

方法一：暴力枚举​

方法二：哈希表​

图解示例​

Java 代码实现​

复杂度分析​

易错点​

相关题目​

49. 字母异位词分组 (Group Anagrams)​

题目描述​

解题思路​

方法一：排序法​

方法二：计数法​

图解示例​

Java 代码实现​

复杂度分析​

易错点​

相关题目​

128. 最长连续序列 (Longest Consecutive Sequence)​

题目描述​

解题思路​

方法一：排序法（非最优）​

方法二：哈希集合（最优）​

图解示例​

Java 代码实现​

复杂度分析​

正确性证明​

易错点​

相关题目​

1. 两数之和 (Two Sum)

题目描述

解题思路

方法一：暴力枚举

方法二：哈希表

图解示例

Java 代码实现

复杂度分析

易错点

相关题目

49. 字母异位词分组 (Group Anagrams)

题目描述

解题思路

方法一：排序法

方法二：计数法

图解示例

Java 代码实现

复杂度分析

易错点

相关题目

128. 最长连续序列 (Longest Consecutive Sequence)

题目描述

解题思路

方法一：排序法（非最优）

方法二：哈希集合（最优）

图解示例

Java 代码实现

复杂度分析

正确性证明

易错点

相关题目