“需要快速判断某个值是否出现过” → 哈希。“两个位置一起移动、避免重复枚举” → 双指针。“数组里找两数关系、去重、原地操作” → 优先想 HashMap / Set / 双指针。Part A数组 HashMap / Set1. 数组到底是什么数组本质上是一段连续存储的同类型/同一逻辑集合数据。nums[1,2,3,4]按下标访问O(1)尾部 append均摊 O(1)中间插入O(n)中间删除O(n)查找某个值O(n)严格来说 Python list 不是传统意义上的固定长度数组它更接近动态数组但在 LeetCode 和机考中我们直接把它当数组使用。2.HashMap / Set 是什么d{}sset()dict→ key:valueset→ 只有 keyHash 查找是平均 O(1)不是绝对 O(1)。理论最坏情况下由于哈希冲突等原因性能可能退化。什么时候应该想到哈希是否出现过 重复 频率 计数 两数之和 映射关系 第一次出现位置 字符统计 O(n)内查找尤其是“数组里找两个数满足某种关系。”因为 Set 中不能存在重复元素。所以 Set 最典型的用途就是去重 快速判断某个元素是否存在。什么是 Hash Table为什么查询快哈希表是一种通过哈希函数将 Key 映射到存储位置的数据结构底层通常基于桶数组实现。在查询一个 Key 时首先计算 Key 的 hash 值再根据 hash 值定位到对应的 bucket而不需要像线性表一样从头遍历因此在哈希分布比较均匀的情况下查找、插入和删除的平均时间复杂度可以达到 O(1)。但是不同 Key 可能映射到同一个位置这叫哈希冲突。常见解决方式包括链地址法和开放寻址法。因此哈希表的 O(1) 一般指平均时间复杂度极端冲突情况下性能可能退化。为什么 HashSet 查询是 O(1)因为 HashSet 通常基于哈希表实现。查询元素时不是遍历 Set 中所有元素而是先计算元素的 hash 值通过 hash 值直接定位到对应的 bucket再进行必要的比较所以平均时间复杂度是 O(1)。哈希表本质上干的事情就是把“按内容查找”转换成了“算出位置后按位置查找”。List 查找 May 在哪 ↓ A → B → C → D → May O(n)HashSet 查找 May 在哪 ↓hash(May)↓ bucket7↓ 直接去 bucket7平均 O(1)Part B双指针双指针到底是什么双指针严格来说不是数据结构而是一种遍历技巧。核心思想不让两个位置彼此独立地枚举而是根据题目性质让两个指针有规律地移动。常见两类。左右指针L → ← R有序数组 回文 两数之和 盛水快慢指针slow → fast-----例如原地删除 移动零 链表环 去重什么时候应该想到双指针有序数组 两个数满足某关系 原地修改 删除元素 去重 移动元素 首尾比较 回文 区间收缩“要求 O(1) 额外空间并原地修改数组”尤其要想到快慢指针哈希练习LeetCode 1. 两数之和双指针练习LeetCode 167. 两数之和 II练习题练习 1LeetCode 217. 存在重复元素练习 2LeetCode 283. 移动零 快慢指针核心思想用一个指针 i记录“下一个非零元素应该放的位置”遍历数组把非零元素往前挪最后把剩余位置补 0。练习 3LeetCode 49. 字母异位词分组 hint同一组字符串拥有相同的 key练习 4LeetCode 15. 三数之和机考视角通常包装订单ID是否重复 用户编号配对 设备记录去重 字符串统计 按照某规则找到两个元素 区间两端不断收缩常见优化路线双循环 O(n²)↓ HashMap/Set ↓ O(n)数组排序 ↓ 左右双指针是否有优化空间 是否可以利用有序性 → 双指针面试手撕训练今天选三数之和最直接的方法是三重循环枚举三个元素时间复杂度 O(n³)数据量大时不可接受。我可以先对数组排序然后固定第一个数字把剩下的问题转换为有序数组的两数之和。对于剩余区间使用左右双指针如果三数之和小于 0则左指针右移如果大于 0则右指针左移。这样每固定一个元素剩余部分只需要 O(n) 扫描因此整体时间复杂度降低为 O(n²)。这道题还需要重点处理重复答案所以固定元素以及找到答案后都需要跳过相同值。Cheat SheetDay 1HashMap / Set看到这些想到哈希 出现过没有 重复 计数 频率 映射关系 两数之和 快速查找Pythonseenset()ifxinseen:...seen.add(x)Dict d{} d[key]valueifkeyind:...复杂度通常查询平均 O(1)插入平均 O(1)删除平均 O(1)空间O(n)双指针左右指针识别信号 有序数组 首尾比较 两数关系 回文 区间收缩模板left0rightlen(nums)-1whileleftright:if...:left1else:right-1快慢指针识别信号原地修改 删除 去重 移动元素模板slow0forfastinrange(len(nums)):ifcondition:nums[slow]nums[fast]slow1两个判断需要把“查找”从 O(n) 降下来 → 考虑 Hash。两个变量存在单调关系不需要所有组合都枚举 → 考虑双指针。