当双层for循环中内层仅查找满足条件的单个元素（如相等、和为target），而非必须遍历所有配对，且存在重复扫描已处理数据的情况，就该怀疑O(n²)可优化；典型解法是用哈希表将内层O(n)查找降为O(1)，或利用有序性+双指针压缩至O(n)。
什么时候该怀疑 O(n²) 是可以优化的？
当你的双层 for 循环里，内层只在找“某个满足条件的元素”（比如相等、和为 target、最近的更大值），而不是必须遍历全部配对时，大概率存在降阶空间。典型信号是：内层循环每次都在重复扫描前面/后面已处理过的数据，且判断逻辑只依赖单个目标值或简单聚合（如 sum、max）。
用哈希表替代内层遍历的常见模式
核心思路：把「需要回头查」的信息提前存进 dict 或 set，让查找从 O(n) 降到 O(1)。最典型的是两数之和问题——原来暴力解法是固定 i，再扫 j > i 找 nums[j] == target - nums[i]；优化后边遍历边存 nums[i]，每次只需查 target - nums[current] 在不在字典里。
- 适用场景：
two-sum、subarray-sum-equals-k（前缀和 + 哈希）、去重统计类问题 - 注意键值设计：存什么做 key（如数值、前缀和）、value 存什么（索引、频次）要匹配后续查询需求
- 边界易错：是否允许重复使用同一元素？索引是否需严格递增？这些会决定你是边存边查，还是先建好哈希再查
双指针为什么能砍掉一维循环？
当数组有序，或你能安全排序（不破坏解的合法性），且目标关系具有单调性（比如两数和变大 → 左指针右移 / 右指针左移能收敛），双指针就能把嵌套循环压成单次扫描。它不是靠空间换时间，而是靠数据内在顺序约束搜索方向。
- 典型错误：对无序数组硬上双指针，结果漏解 —— 必须确认排序不影响答案，或原题明确给出 sorted 输入
- 三数之和的常见坑：
while i 这类去重逻辑，下标越界或漏判相邻重复值很常见 - 性能差异：O(n²) 变 O(n)，但前提是排序 O(n log n) 可接受；如果原始顺序敏感（如要求返回原索引），就得额外记录位置
滑动窗口解决“连续子数组”类 O(n²) 问题
如果你的双层循环本质是在枚举所有起点和终点（即所有子数组），而判定条件支持增量更新（比如窗口和、字符频次、最大值），那滑动窗口能把内层循环变成均摊 O(1) 的伸缩操作。
- 关键识别点：问题描述含 “连续”、“子数组”、“子串”，且约束是可累积的（如和 ≤ k、不含重复字符）
- 左边界移动条件必须明确：是 while 还是 if？收缩时机是 sum 超限后立刻动，还是等右边界停稳再动？这个逻辑错一点，窗口就失效
- 别忘了初始化：窗口通常从空开始（
left = right = 0），不是从[0,0]开始就默认有元素
实际降阶成败，往往卡在对“问题结构”的准确识别——是查重？是求和约束？是顺序相关？还是连续性要求？比记住算法模板更重要的是，在写第一行 for 前，先问自己：内层循环真的每个 j 都不可跳过吗？
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
