Day 6 - 哈希表进阶

📅 日期：2026年1月13日
🎯 主题：哈希表进阶 + 集合操作

今日题目

题目1：最长连续序列 (Longest Consecutive Sequence)

难度：⭐⭐ 中等

链接：LeetCode 128. 最长连续序列

题目描述

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

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

示例：

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

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

提示：

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

解题思路

方法一：哈希表 + 集合 ✅ 推荐

核心思想：

1. 将所有数字存入哈希集合（Set）中，实现 O(1) 的查找
2. 遍历数组，对于每个数字 num，检查它是否是某个连续序列的起点
3. 判断起点：如果 num - 1 不在集合中，说明 num 是某个连续序列的起点
4. 从起点开始，不断查找 num + 1 是否在集合中，计算连续序列的长度
5. 更新最长连续序列的长度

关键点：

• 使用 Set 存储所有数字，实现 O(1) 查找
• 只从连续序列的起点开始计算，避免重复计算
• 时间复杂度：O(n)，每个数字最多被访问两次（一次作为起点，一次作为其他序列的一部分）

方法二：排序

核心思想：

1. 对数组排序
2. 遍历排序后的数组，统计连续序列的长度
3. 时间复杂度：O(n log n)，不满足题目要求的 O(n)

代码实现

方法一：哈希表 + 集合

import java.util.*;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // 将所有数字存入 Set 中
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int longestStreak = 0;
        
        // 遍历数组
        for (int num : numSet) {
            // 如果 num - 1 不在集合中，说明 num 是某个连续序列的起点
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                
                // 从起点开始，不断查找下一个连续数字
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                
                // 更新最长连续序列的长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        
        return longestStreak;
    }
}

方法二：排序

import java.util.*;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // 排序
        Arrays.sort(nums);
        
        int longestStreak = 1;
        int currentStreak = 1;
        
        // 遍历排序后的数组
        for (int i = 1; i < nums.length; i++) {
            // 如果当前数字等于前一个数字，跳过（处理重复数字）
            if (nums[i] == nums[i - 1]) {
                continue;
            }
            
            // 如果当前数字等于前一个数字 + 1，连续序列继续
            if (nums[i] == nums[i - 1] + 1) {
                currentStreak++;
            } else {
                // 连续序列中断，更新最长长度
                longestStreak = Math.max(longestStreak, currentStreak);
                currentStreak = 1;
            }
        }
        
        return Math.max(longestStreak, currentStreak);
    }
}

复杂度分析

• 时间复杂度：
  • 哈希表方法：O(n)，每个数字最多被访问两次
  • 排序方法：O(n log n)，排序的时间复杂度
• 空间复杂度：
  • 哈希表方法：O(n)，需要存储所有数字
  • 排序方法：O(1)，如果排序是原地排序

---

题目2：存在重复元素 II (Contains Duplicate II)

难度：⭐ 简单

链接：LeetCode 219. 存在重复元素 II

题目描述

给你一个整数数组 nums 和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，满足 nums[i] == nums[j] 且 abs(i - j) <= k。如果存在，返回 true；否则，返回 false。

示例：

输入：nums = [1,2,3,1], k = 3
输出：true
解释：索引 0 和 3 处的元素相同，且 abs(0 - 3) = 3 <= k

输入：nums = [1,0,1,1], k = 1
输出：true
解释：索引 2 和 3 处的元素相同，且 abs(2 - 3) = 1 <= k

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

提示：

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

解题思路

方法一：哈希表 + 滑动窗口 ✅ 推荐

核心思想：

1. 使用哈希表存储每个数字及其最近出现的索引
2. 遍历数组，对于每个数字 nums[i]：
   • 如果该数字已经在哈希表中，检查当前索引与上次出现的索引的差值是否 <= k
   • 如果差值 <= k，返回 true
   • 否则，更新该数字的最新索引
3. 如果遍历完都没有找到满足条件的重复元素，返回 false

关键点：

• 使用哈希表存储 数字 -> 索引 的映射
• 只保留最近出现的索引，因为如果更早的索引不满足条件，更晚的索引也不会满足
• 滑动窗口的思想：维护一个大小为 k+1 的窗口

方法二：暴力枚举

核心思想：

1. 对于每个元素，检查其后 k 个元素中是否有相同的
2. 时间复杂度：O(nk)，不推荐

代码实现

方法一：哈希表 + 滑动窗口

import java.util.*;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 使用哈希表存储数字及其最近出现的索引
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            
            // 如果该数字已经出现过
            if (map.containsKey(num)) {
                // 检查当前索引与上次出现的索引的差值
                int lastIndex = map.get(num);
                if (i - lastIndex <= k) {
                    return true;  // 找到满足条件的重复元素
                }
            }
            
            // 更新该数字的最新索引
            map.put(num, i);
        }
        
        return false;  // 没有找到满足条件的重复元素
    }
}

方法二：滑动窗口优化（固定窗口大小）

import java.util.*;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 使用 Set 维护一个大小为 k+1 的滑动窗口
        Set<Integer> set = new HashSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            // 如果窗口大小超过 k+1，移除最左边的元素
            if (i > k) {
                set.remove(nums[i - k - 1]);
            }
            
            // 如果当前元素已经在窗口中，说明找到了满足条件的重复元素
            if (set.contains(nums[i])) {
                return true;
            }
            
            // 将当前元素加入窗口
            set.add(nums[i]);
        }
        
        return false;
    }
}

复杂度分析

• 时间复杂度：
  • 哈希表方法：O(n)，需要遍历数组一次
  • 滑动窗口方法：O(n)，每个元素最多被添加和删除一次
• 空间复杂度：
  • 哈希表方法：O(min(n, k))，最多存储 k+1 个元素
  • 滑动窗口方法：O(min(n, k))，Set 最多存储 k+1 个元素

---

今日总结

学到了什么？

1. 哈希集合的应用：使用 Set 实现 O(1) 的查找，优化算法时间复杂度
2. 连续序列判断技巧：只从序列起点开始计算，避免重复计算
3. 滑动窗口 + 哈希表：结合滑动窗口和哈希表解决距离限制问题
4. 索引维护：使用哈希表维护元素的最新索引，解决索引相关问题

关键技巧

技巧	适用场景	时间复杂度	空间复杂度
Set 查找优化	需要快速判断元素是否存在	O(1) 查找	O(n)
起点判断	连续序列、区间问题	O(n)	O(n)
滑动窗口 + 哈希表	距离限制的重复元素问题	O(n)	O(k)
索引维护	需要记录元素位置的问题	O(n)	O(n)

哈希表进阶操作要点

1. Set 的使用场景：

   • 快速判断元素是否存在
   • 去重操作
   • 集合运算（交集、并集、差集）

2. 连续序列问题：

   • 使用 Set 存储所有数字
   • 只从序列起点开始计算
   • 判断起点：num - 1 不在集合中

3. 滑动窗口技巧：

   • 维护固定大小的窗口
   • 使用 Set 或 Map 存储窗口内的元素
   • 窗口移动时更新数据结构

4. 索引维护：

   • 使用 Map 存储 元素 -> 索引 的映射
   • 只保留最新或最相关的索引
   • 根据问题需求更新索引

5. 常见错误：

   • 忘记处理空数组或边界情况
   • 重复计算连续序列
   • 滑动窗口大小控制错误
   • 索引更新时机不当

相似题目推荐

• 存在重复元素 - 判断是否存在重复元素
• 存在重复元素 III - 滑动窗口 + TreeSet
• 无重复字符的最长子串 - 滑动窗口 + 哈希表
• 和为 K 的子数组 - 前缀和 + 哈希表

明日计划

• Day 7 字符串基础
• 练习：反转字符串、有效的字母异位词（复习）