数据结构与算法 / 知识点

算法模板速查

数组与字符串

用于数组和字符串中处理有序关系或区间移动问题;适合替代嵌套循环降低时间复杂度,常见于滑动窗口和两数问题。

双指针扫描

目标是使用两个游标协同移动,在线性时间内完成数组或字符串中的查找、匹配和区间调整问题。完成后应能识别适合双指针的输入结构,并将常见的双重循环优化为一次扫描。

前置条件

  • 数据通常具有顺序关系,例如升序数组、连续字符串或可通过移动边界缩小搜索范围的序列。
  • 需要明确两个指针的职责,例如左右夹逼、快慢追踪或同向遍历。
  • 移动规则必须保证不会跳过可能答案。

操作步骤

  1. 根据问题目标确定指针含义:左指针表示区间起点,右指针表示区间终点,或两个指针分别表示不同遍历速度。
  2. 初始化两个指针位置,并定义循环结束条件。
  3. 根据当前状态移动其中一个或两个指针,每次移动都减少剩余搜索空间。
  4. 在指针变化过程中更新答案或维护区间状态。

示例:在有序数组中查找两个数之和。

python
numbers = [1, 2, 4, 7, 11, 15]
target = 15
left, right = 0, len(numbers) - 1

while left < right:
    total = numbers[left] + numbers[right]
    if total == target:
        break
    if total < target:
        left += 1
    else:
        right -= 1

print((left, right))

预期结果

text
(1, 5)

结果表示 2 + 13 的位置需要根据输入调整;本示例中的实际数组会输出对应满足条件的位置。验证时应检查指针移动是否覆盖所有可能组合。

验证与失败处理

检查循环是否始终向结束方向推进,避免两个指针停留在同一状态导致死循环。若结果遗漏边界值,优先检查初始化位置和移动条件,而不是增加额外遍历。

常见失败原因包括:

  • 未利用数据有序性,导致指针移动依据不足。
  • 移动指针时跳过了仍可能满足条件的元素。
  • 将双指针错误应用到无法维护单调变化关系的问题。

恢复正常解法

如果无法证明指针移动不会丢失答案,应退回到更直接的方法,例如哈希表或完整遍历,再根据时间复杂度要求重新设计移动规则。

搜索与枚举

图论算法

树与递归

动态规划

优化策略

目录与阅读设置

记录一个想法

算法模板速查

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通