• 完成哈希表相关题目的学习
• 这个阶段甚至还能学到新的函数（
• 依旧背点单词
• 继续学 Java

总结

核心心法是： 牺牲空间换取时间

如果不用哈希表，你想在数组里找一个数字，只能从头到尾用 for 循环遍历，时间复杂度是 O(N)（很慢）。 而哈希表的核心作用就是 “瞬间定位”。它牺牲了一点点内存（空间），换来了 O(1)（极速）的查找时间

当你在读算法题的题目要求时，如果看到了以下 “关键词”，脑子里第一反应就应该是哈希表：

• 看到 “统计...出现的次数 / 频率” ➡️ 用 HashMap 作计数器
• 看到 “有没有 / 是否存在 / 是否重复” ➡️ 用 HashSet 去重或查岗
• 看到 “配对 / 两数相加等于某值” ➡️ 用 HashMap 作记事本
• 看到 “归类 / 分组” ➡️ 用 HashMap + ArrayList 作收纳盒
• 看到 “要求时间复杂度为 O(N) 内完成查找” ➡️ 别想了，99% 是逼着你用哈希表

⚠️ 什么时候【绝对不要】用哈希表？

哈希表虽然强，但它有一个致命弱点：无序。

• 如果题目要求你 “找出最大/最小的前 K 个元素”，你应该用优先队列（堆）。
• 如果题目要求你 “保持数据输入时的顺序”，普通的 HashMap 会把顺序打乱（除非你用 LinkedHashMap）。
• 如果题目说 “内存非常受限”，哈希表由于底层要维护数组和链表/红黑树，会占用较多额外空间，这时候可能要考虑双指针或者原地排序

例子 最长连续数列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题

class Solution {  
    public int longestConsecutive(int[] nums) {  
        Set<Integer> st = new HashSet<>();  
        for (int num : nums) {  
            st.add(num);  
        }  
  
        int ans = 0;  
        for (int x : st) {  
            if (st.contains(x - 1)) {  
                continue;  
            }  
            int y = x + 1;  
            while (st.contains(y)) {  
                y++;  
            }  
            ans = Math.max(ans, y - x);  
        }  
        return ans;  
    }  
}

运行流程： 为了做到 O(n) 的时间复杂度，以下为两个关键的优化点

• 把 nums 中的数都放入一个哈希集合中，这样可以 O(1) 判断数字是否在 nums 中
• 如果 x−1 在哈希集合中，则不以 x 为起点。为什么？因为以 x−1 为起点计算出的序列长度，一定比以 x 为起点计算出的序列长度要长！这样可以避免大量重复计算。比如 nums=[3,2,4,5]，从 3 开始，我们可以找到 3,4,5 这个连续序列；而从 2 开始，我们可以找到 2,3,4,5 这个连续序列，一定比从 3 开始的序列更长 在第一次遍历st时 查找有没有 x 是否为序列的开头，如果还有比 x 更小的数，说明 x 不是本序列的第一个数，所以直接 continue 跳过

当找到序列的开头 x 后，开始执行下一个循环，在哈希表里查询 x 的下一位 y 最终找到序列的最后一位 y 最后返回 ans y-x 正好是序列的长度