1. 两数之和

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return []
        
        hash_map = {}
        for index, num in enumerate(nums):
            c = target - num
            if c in hash_map:
                return [hash_map[c], index]
            hash_map[num] = index
        return []

1. 暴力解法：最简单的想法是双重循环，检查每对数字的和是否等于目标值。时间复杂度O(n²)，太慢。

2. 优化思路：

   • 我们需要快速判断 target - 当前数字 是否在数组中

   • 需要知道这个数字的索引

   • 这正好是哈希表（字典）的强项：O(1)时间查找

3. 具体实现：

   数组：[2, 7, 11, 15]，目标值：9
   
   遍历过程：
   第1次：num=2, index=0
      补数c=9-2=7
      7不在哈希表中，存入{2:0}
   
   第2次：num=7, index=1
      补数c=9-7=2
      2在哈希表中！返回[hash_map[2], 1] = [0, 1]

4. 为什么有效：

   • 我们边遍历边记录已经访问过的数字

   • 对于当前数字，我们查找的是"之前是否遇到过我的补数"

   • 这样只需要一次遍历就能解决问题

49.字母异位词分类

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hash_map = {}
        
        for s in strs:
            key = "".join(sorted(s))
            if key in hash_map:
                hash_map[key].append(s)
            else:
                hash_map[key] = [s]
        
        return list(hash_map.values())

1. 关键观察：字母异位词排序后是一样的！

   "eat" -> "aet"
   "tea" -> "aet"
   "ate" -> "aet"

2. 分组策略：

   • 我们可以用排序后的字符串作为"签名"

   • 相同签名的单词就是一组

   • 哈希表的键就是这个签名，值就是单词列表

3. 具体实现：

   输入：["eat","tea","tan","ate","nat","bat"]
   
   处理过程：
   "eat" -> 排序得"aet" -> 分组1：["eat"]
   "tea" -> 排序得"aet" -> 分组1：["eat","tea"]
   "tan" -> 排序得"ant" -> 分组2：["tan"]
   "ate" -> 排序得"aet" -> 分组1：["eat","tea","ate"]
   "nat" -> 排序得"ant" -> 分组2：["tan","nat"]
   "bat" -> 排序得"abt" -> 分组3：["bat"]
   
   结果：[["eat","tea","ate"],["tan","nat"],["bat"]]

4. 为什么有效：

   • 排序操作让字母异位词有了统一的表示

   • 哈希表高效地实现了分组功能

128. 最长连续序列

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        nums_set = set(nums)
        nums_l = len(nums_set)

        for num in nums_set:
            if num - 1 in nums_set:
                continue

            current_num = num
            current_streak = 1

            while current_num + 1 in nums_set:
                current_num += 1
                current_streak += 1

            longest_streak = max(longest_streak, current_streak)

            if longest_streak * 2 >= nums_l:
                break

        return longest_streak

1. 直接排序的局限性：

   • 排序需要O(n log n)时间，不满足要求

   • 我们需要O(n)解法

2. 核心洞察：

   • 只需要知道一个数字"是否存在"，不需要知道位置

   • 查找操作应该是O(1)的 → 使用集合（set）

   • 为了避免重复计算，只从"序列起点"开始计数

3. 如何判断起点：

   • 如果一个数字的前一个数在集合中，它不是起点

   • 只有 num-1 不在集合中的数字，才是序列起点

   例子：[100, 4, 200, 1, 3, 2]
   集合：{100, 4, 200, 1, 3, 2}
   
   检查4：3在集合中吗？在 → 4不是起点，跳过
   检查1：0在集合中吗？不在 → 1是起点

4. 算法步骤：

   输入：[100, 4, 200, 1, 3, 2]
   
   1. 转为集合：{100, 4, 200, 1, 3, 2}
   2. 遍历集合：
      - 100：99不在集合 → 是起点
        从100开始向后找：100, 101不存在 → 长度1
      
      - 4：3在集合 → 不是起点，跳过
      
      - 200：199不在集合 → 是起点
        从200开始向后找：200, 201不存在 → 长度1
      
      - 1：0不在集合 → 是起点
        从1开始向后找：1,2,3,4都存在，5不存在 → 长度4
   
   3. 最长长度是4（序列1,2,3,4）

5. 优化技巧：

   • 如果当前最长序列长度已经超过剩余数字的一半，可以提前结束

   • 因为剩下的数字不可能组成更长的序列了

6. 为什么是O(n)：

   • 每个数字最多被访问两次：一次在遍历中，一次在向后查找中

   • 内层while循环虽然看起来嵌套，但每个数字只会在某个序列中被访问一次