解题切入点
算法解题思维导图：如何在陌生题目中快速定位算法思想¶
本文的核心目标不是"记住算法怎么写"，而是"理解为什么要这样设计"。每种算法都从题眼识别开始，经过暴力分析，最终推导出优化路径。读完之后，你应该能在陌生题目上复现这个推导过程，而不是靠记忆匹配模板。
哈希表¶
题眼抓取¶
看到"两数之和""是否存在某个值""频次统计""去重"这类词，都应该立刻联想到哈希表。更精确的触发条件是：题目要求你在一个集合中做"存不存在"或"出现了多少次"的查询，而这个查询需要反复执行。单次查询用遍历就够了，但当查询量与数据量同阶时，O(n) 的遍历叠加起来就变成了 O(n²)，这正是哈希表介入的信号。
核心本质¶
哈希表的本质是用空间换时间：把"在哪里"这个问题预先编码成一个地址，把 O(n) 的线性搜索压缩成 O(1) 的直接寻址。它的有效性来自于哈希函数的存在，而不是数据的有序性——这也是它与二分查找的根本区别：二分依赖顺序，哈希不依赖。
暴力 → 优化的推导路径¶
暴力做法是双层循环：外层枚举每个元素，内层扫描整个数组寻找配对。瓶颈在于内层的"查找"是 O(n)，而这个查找本可以用 O(1) 完成。关键观察是：查找操作的目标（即"我需要找什么值"）在外层循环的当前步骤是已知的，因此可以预先把所有值存入哈希表，把"扫描"变成"查表"。
代表题：两数之和（LeetCode 1）¶
给定数组 nums 和目标值 target，找出两个下标使其对应元素之和等于 target。
读题时注意到"找两个数""和等于某个值"，这是典型的配对查找，题眼指向哈希表。暴力是 O(n²) 双层枚举。优化的观察是：当我遍历到 nums[i] 时，我需要的配对值 target - nums[i] 是确定的，只需要查一下它是否出现过。于是用一个哈希表边遍历边存储，每步做一次 O(1) 查询，总复杂度 O(n)。
def twoSum(nums, target):
seen = {} # 值 → 下标
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
双指针¶
题眼抓取¶
看到"有序数组""两个数的关系""回文""原地操作不用额外空间"，应联想到双指针。更具体的触发条件是：问题涉及两个位置之间的关系，而这两个位置的移动方向有规律可循——要么相向（对撞指针），要么同向（快慢指针）。
核心本质¶
双指针的本质是利用单调性剪枝：当两个指针的某种关系（如和、差、距离）随指针移动单调变化时，不需要枚举所有指针组合，只需要按照"当前状态告诉我往哪移"的规则单向推进。它把 O(n²) 的枚举压缩为 O(n) 的单次扫描。
暴力 → 优化的推导路径¶
暴力是双层循环枚举所有 (i, j) 对。瓶颈在于大量的组合是"明显不可能是答案"的，但暴力逐一检查了它们。关键观察是：如果数组有序，当左指针 l 和右指针 r 的和偏大时，只有 r 向左移才可能让和减小；偏小时只有 l 向右移。这意味着每一步都能排除至少一半的候选，整体线性推进。
代表题：三数之和（LeetCode 15）¶
找出数组中所有和为零的三元组（不重复）。
题眼是"有序""三个数的和""不重复"。先排序，外层固定第一个数，内层用对撞双指针处理剩余两数的配对问题。当两指针的和偏大就右指针左移，偏小就左指针右移，相遇时终止。整体 O(n²)，相比暴力 O(n³) 少一个量级。重复元素的跳过也依赖排序后的单调性。
def threeSum(nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue # 跳过重复的第一个数
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s == 0:
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]: l += 1
while l < r and nums[r] == nums[r-1]: r -= 1
l += 1; r -= 1
elif s < 0:
l += 1
else:
r -= 1
return res
滑动窗口¶
题眼抓取¶
看到"连续子数组或子串""满足某个条件的最长/最短""窗口内的统计量"，应联想到滑动窗口。区分滑动窗口和双指针的关键在于：滑动窗口的两个指针都向同一方向移动（左指针永远不超过右指针），维护的是一个区间的某种聚合状态；双指针通常是对撞或追逐关系。
核心本质¶
滑动窗口的本质是增量维护区间状态：右指针扩展时加入新元素，左指针收缩时移除旧元素，每步只处理变化的那一个元素，而不是重新计算整个窗口。有效性来自于"窗口状态随指针单调变化"这个性质，即右扩使窗口更满足条件、左缩使窗口更不满足条件（或反之）。
暴力 → 优化的推导路径¶
暴力枚举所有 (l, r) 对并计算窗口统计量，瓶颈是每次移动右指针后需要重新扫描窗口。关键观察是：相邻两个窗口 [l, r] 和 [l, r+1] 只相差一个元素，窗口状态可以从上一步 O(1) 更新而来，不需要重新扫描。
代表题：无重复字符的最长子串（LeetCode 3）¶
找出不含重复字符的最长子串的长度。
题眼是"最长子串""无重复"。右指针扩展加入新字符，用哈希表记录字符频次；当某字符频次超过 1（出现重复），左指针收缩直到重复消除。每个字符最多被左右指针各访问一次，O(n)。
def lengthOfLongestSubstring(s):
freq = {}
l = ans = 0
for r, c in enumerate(s):
freq[c] = freq.get(c, 0) + 1
while freq[c] > 1: # 窗口内有重复
freq[s[l]] -= 1
l += 1
ans = max(ans, r - l + 1)
return ans
前缀和¶
题眼抓取¶
看到"区间求和""子数组和等于某值""多次查询某段区间"，应联想到前缀和。触发的核心条件是：数组静态不变，但需要反复查询不同区间的聚合值（和、积、异或）。如果数组会动态更新，则需要升级到树状数组或线段树。
核心本质¶
前缀和的本质是把"区间查询"转化为"端点相减"：用 O(n) 的预处理换取每次 O(1) 的区间查询。它是增量维护思想的最简单形式，有效性来自于"区间信息可以由两个前缀信息相减得出"这个可拆分性。
暴力 → 优化的推导路径¶
暴力每次查询 sum(l, r) 都要从 l 扫描到 r，单次 O(n)，多次查询变成 O(nq)。关键观察是：sum(l, r) = sum(0, r) - sum(0, l-1)，而 sum(0, i) 对所有 i 可以一次性预计算，把重复计算变成两次 O(1) 的查表。
代表题：和为 K 的子数组（LeetCode 560）¶
统计和为 k 的连续子数组的个数。
题眼是"子数组和等于某值""计数"。设前缀和数组为 P，则 sum(i, j) = P[j] - P[i-1] = k 等价于 P[i-1] = P[j] - k。遍历 j 时，只需查哈希表中 P[j] - k 出现了多少次（即有多少个合法的左端点）。这里前缀和与哈希表联合使用，前缀和负责把区间问题转化为端点问题，哈希表负责 O(1) 查找配对。
def subarraySum(nums, k):
count = {0: 1} # 前缀和 → 出现次数
prefix = ans = 0
for x in nums:
prefix += x
ans += count.get(prefix - k, 0)
count[prefix] = count.get(prefix, 0) + 1
return ans
二分查找¶
题眼抓取¶
看到"有序数组""找某个值或边界""答案具有单调性（满足条件的最大/最小值）"，应联想到二分查找。特别重要的一个变体触发词是"最小化最大值"或"最大化最小值"——这类问题的答案空间本身是有序的，可以对答案二分而不是对输入二分。
核心本质¶
二分查找的本质是利用单调性每次排除一半的搜索空间：在每一步，当前的中间值要么告诉你答案在左半边，要么告诉你在右半边，因此搜索空间以指数速度缩小。有效性的前提是"判断函数具有单调性"——满足条件的所有值聚集在一侧，不满足的在另一侧。
暴力 → 优化的推导路径¶
暴力是线性扫描整个搜索空间，O(n)。关键观察是：如果能判断当前中间值是否满足条件，且满足/不满足的区域在空间上连续，则每次判断就能排除一半候选，把 O(n) 变成 O(log n)。
代表题：在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）¶
给定有序数组，找目标值的起始和结束位置。
题眼是"有序数组""边界位置"。两次二分：第一次找"第一个 ≥ target 的位置"，第二次找"第一个 > target 的位置"，后者减一即为结束位置。边界二分的模板需要把握清楚"收缩左边界还是右边界"的逻辑，核心判断条件决定了最终落点。
def searchRange(nums, target):
def lower_bound(t): # 第一个 >= t 的位置
l, r = 0, len(nums)
while l < r:
m = (l + r) // 2
if nums[m] < t: l = m + 1
else: r = m
return l
start = lower_bound(target)
if start == len(nums) or nums[start] != target:
return [-1, -1]
return [start, lower_bound(target + 1) - 1]
单调栈¶
题眼抓取¶
看到"下一个更大元素""左边第一个比我大的""柱状图面积""括号匹配"，应联想到单调栈。核心触发条件是：对每个元素，需要找到它左边或右边第一个满足大小关系的元素，而且需要对所有元素都做这个操作。
核心本质¶
单调栈的本质是：当一个新元素使栈内旧元素"永远不可能再成为答案"时，立刻淘汰它并记录答案。具体来说，如果我们要找每个元素"右边第一个更大值"，那么当新元素 x 入栈时，所有比 x 小的栈内元素都找到了答案（就是 x），可以立刻出栈。每个元素入栈出栈各一次，总代价 O(n)。
与单调队列的区别在于：单调栈只在一端操作，没有"过期"的概念，淘汰的理由纯粹是单调性；单调队列在两端操作，同时处理单调性和窗口过期两个约束。
暴力 → 优化的推导路径¶
暴力对每个元素向右扫描找第一个更大值，O(n²)。关键观察是：扫描过程中有大量重复。当我们从左往右处理时，对于还没有找到答案的元素（它们在栈里等待），一旦来了一个更大的新元素，所有等待中的比它小的元素同时找到答案。这个"批量结算"使每个元素只被处理一次。
代表题：柱状图中最大的矩形（LeetCode 84）¶
给定柱状图的高度数组，找出能容下的最大矩形面积。
题眼是"向左/右延伸""第一个比我矮的柱子"。对每根柱子，它能向左右延伸的边界由其两侧第一个更矮的柱子决定。用单调递增栈：当新柱子比栈顶矮时，栈顶柱子找到了右边界（新柱子）和左边界（新栈顶），立刻计算面积。两端加哨兵（高度为0）简化边界处理。
def largestRectangleArea(heights):
heights = [0] + heights + [0] # 两端哨兵
stack = [0] # 单调递增栈，存下标
ans = 0
for i in range(1, len(heights)):
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
ans = max(ans, h * w)
stack.append(i)
return ans
单调队列¶
题眼抓取¶
看到"滑动窗口内的最大值/最小值""长度受限的子数组极值""固定窗口滑动"，应联想到单调队列。与普通滑动窗口的区别在于：普通滑动窗口维护的是频次或求和等线性聚合量；单调队列维护的是极值，而极值不能简单地在移除元素时更新（你无法知道移除最大值后谁是新最大值）。
核心本质¶
单调队列的本质是：用单调性提前永久淘汰"在数值上更劣、在有效期上更短"的候选，把每个右端点处的"扫描窗口找极值"变成 O(1) 的队头读取，实现增量维护。队尾弹出对应单调性淘汰，队头弹出对应过期淘汰，两者共同保证队头始终是当前窗口的最优候选。
暴力 → 优化的推导路径¶
暴力固定右端点后扫描整个窗口找极值，O(nk)。关键观察是：当新元素 x 入队时，所有在 x 左边且值比 x 更大（若找最小值则更小）的旧候选，同时满足"数值更劣"和"有效期更短"两个条件，未来永远不可能被选中，可以立刻永久丢弃。这使得整个过程的总操作次数不超过 2n。
代表题：滑动窗口最大值（LeetCode 239）¶
给定数组和窗口大小 k，返回每个滑动窗口的最大值。
题眼是"固定大小窗口""最大值"。单调递减队列：新元素入队前弹出所有比它小的队尾（它们永远不可能是答案），队头若下标过期则弹出，每个窗口直接读队头。
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # 单调递减，存下标
ans = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x: # 队尾更小的永久淘汰
dq.pop()
dq.append(i)
if dq[0] < i - k + 1: # 队头过期
dq.popleft()
if i >= k - 1:
ans.append(nums[dq[0]])
return ans
差分数组¶
题眼抓取¶
看到"对区间批量加减""多次区间更新后查询结果""区间覆盖操作"，应联想到差分数组。它是前缀和的逆操作：前缀和把"单点查询"加速，差分把"区间修改"加速。两者互为对偶，合用时能同时加速修改和查询。
核心本质¶
差分数组的本质是：不直接记录每个位置的值，而是记录相邻位置之间的"变化量"。区间 [l, r] 整体加 v 这个操作，在差分数组上只体现为两个端点的变化（D[l] += v，D[r+1] -= v），最后对差分数组求前缀和即可还原原数组。
暴力 → 优化的推导路径¶
暴力对每个区间更新操作逐个修改数组中的每个元素，单次 O(n)，m 次操作后 O(mn)。关键观察是：一个区间更新操作的影响在差分数组上只集中在两个端点，因为差分数组记录的是"变化"而非"绝对值"。把 O(n) 的区间修改压缩为 O(1) 的端点修改，最后一次性 O(n) 还原。
代表题：航班预订统计（LeetCode 1109）¶
有 n 个航班，m 条预订记录 [first, last, seats] 表示第 first 到 last 航班各预订了 seats 个座位，输出每个航班的预订总量。
题眼是"区间批量加""最终统计每点的值"。对每条记录在差分数组上做两次端点操作，最后求前缀和还原。O(m + n) 远优于暴力的 O(mn)。
def corpFlightBookings(bookings, n):
diff = [0] * (n + 2)
for first, last, seats in bookings:
diff[first] += seats
diff[last + 1] -= seats
# 前缀和还原
ans, cur = [], 0
for i in range(1, n + 1):
cur += diff[i]
ans.append(cur)
return ans
二分查找（答案二分变体）¶
附：二分答案的题眼¶
这是二分查找一个特别值得单独说的变体。当题目问"在满足某个条件下，某个值最大/最小是多少"，且这个值的答案空间是连续整数区间，同时判断"某个值是否可行"本身可以 O(n) 或更快完成时，应对答案空间做二分。
代表题是"分割数组的最大值"（LeetCode 410）：把数组分成 m 段，使各段和的最大值尽量小。答案越大越容易满足（可以分的段数越多），答案越小越难满足——这种单调性就是二分的触发条件。
动态规划¶
题眼抓取¶
看到"最优子结构""重叠子问题""求最大/最小/计数""能否分解成更小的同类问题"，应联想到动态规划。特别是"前 i 个元素的某个最优值""以第 i 个元素结尾的某个最优值"这类状态定义方式，是 DP 最常见的形式。
核心本质¶
动态规划的本质是：把一个大问题的最优解，通过子问题的最优解推导出来，并通过记忆化避免重复计算相同子问题。有效性来自于最优子结构：大问题的最优解由子问题的最优解组合而成，不需要枚举所有方案。
暴力 → 优化的推导路径¶
暴力是递归枚举所有可能的决策序列，指数级复杂度。关键观察是：不同的决策路径可能到达同一个"状态"，而从这个状态出发的最优解是唯一的，不依赖是如何到达这个状态的。因此把"状态 → 最优值"的对应关系记录下来（记忆化），每个状态只计算一次，把指数复杂度压缩为多项式。
代表题：最长递增子序列（LeetCode 300）¶
找出数组中最长的严格递增子序列的长度。
题眼是"子序列（不要求连续）""递增""最长"。定义 dp[i] 为以 nums[i] 结尾的最长递增子序列长度。转移：dp[i] = max(dp[j] + 1) 对所有 j < i 且 nums[j] < nums[i]。基础 DP 是 O(n²)，配合二分查找可以优化到 O(n log n)（维护一个辅助数组，记录长度为 k 的递增子序列的最小末尾值）。
def lengthOfLIS(nums):
dp = [] # dp[i] 表示长度为 i+1 的递增子序列的最小末尾值
for x in nums:
import bisect
pos = bisect.bisect_left(dp, x)
if pos == len(dp):
dp.append(x)
else:
dp[pos] = x # 更新为更小的末尾值
return len(dp)
回溯¶
题眼抓取¶
看到"所有可能的组合/排列/子集""满足条件的所有路径""暴力穷举但需要剪枝"，应联想到回溯。回溯适合"答案需要枚举所有可能"的场景，当问题只需要最优值时通常用 DP；当问题需要列出所有方案时用回溯。
核心本质¶
回溯的本质是深度优先搜索加上撤销操作：沿着一个分支深入，到达终止条件时记录答案，然后撤销最后一步决策，换另一个分支继续。剪枝是回溯的核心优化：在某个中间状态已经明确不可能产生合法答案时，提前终止该分支，避免无效搜索。
暴力 → 优化的推导路径¶
暴力是枚举所有可能的决策序列。回溯的改进在于：不是先生成再过滤，而是在生成过程中实时判断当前路径是否还有可能通向合法答案，不可能时立刻剪掉整棵子树。剪枝的力度决定了实际运行效率，而剪枝的依据来自对问题约束的深刻理解。
代表题：全排列（LeetCode 46）¶
给定不含重复数字的数组，返回所有可能的全排列。
题眼是"所有排列""穷举"。每一步从剩余未选的数中选一个，递归直到选满 n 个数。用 used 数组标记已选元素，回溯时撤销标记。总共 n! 个叶节点，这是问题本身的复杂度下界，回溯无法降低，只能通过剪枝减少无效分支。
def permute(nums):
res, path, used = [], [], [False] * len(nums)
def bt():
if len(path) == len(nums):
res.append(path[:])
return
for i, x in enumerate(nums):
if used[i]: continue
used[i] = True
path.append(x)
bt()
path.pop() # 撤销
used[i] = False # 撤销
bt()
return res
贪心¶
题眼抓取¶
看到"局部最优可以推出全局最优""每步做出不可撤回的最优决策""区间调度""跳跃问题"，应联想到贪心。贪心的难点不在实现，而在于证明局部最优策略的全局正确性——这需要构造反例来反驳，或者用交换论证来证明。
核心本质¶
贪心的本质是：存在一种决策顺序，使得每步的局部最优选择不会妨碍未来做出最优选择，因此无需回溯。与 DP 的区别在于：DP 在每个状态保留多种可能并比较；贪心在每个状态只保留一种选择并直接推进。贪心可以看作 DP 的一种极端简化，条件是决策之间有严格的偏序关系。
暴力 → 优化的推导路径¶
暴力是 DP：穷举所有决策序列取最优。关键观察是：如果能证明在每个决策点，某个特定选择（通常是"最早结束""最大收益""最小代价"之一）不会比其他选择更差，那么就可以放弃 DP 中的"保留多选项"，直接每步选这个最优项。
代表题：跳跃游戏（LeetCode 55）¶
数组每个元素表示从该位置能跳的最远距离，判断能否到达最后一个位置。
题眼是"能否到达""每步可跳范围"。贪心维护"当前能到达的最远位置 maxReach"：遍历每个位置，若当前位置超过 maxReach 则无法到达直接返回 False，否则更新 maxReach = max(maxReach, i + nums[i])。局部最优（尽量延伸可达范围）直接等于全局最优。
def canJump(nums):
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach:
return False
max_reach = max(max_reach, i + jump)
return True
图论 BFS / DFS¶
题眼抓取¶
看到"连通分量""最短路径（无权图）""层序遍历""从某点出发能到达哪里""岛屿数量""拓扑排序"，应联想到图论 BFS/DFS。BFS 和 DFS 的选择依据是：需要最短路径或最少步数时用 BFS（它按层扩展，第一次到达目标时步数最少）；需要遍历所有路径或探测连通性时用 DFS（实现简单，但不保证最短）。
核心本质¶
BFS 的本质是按距离分层扩展，用队列保证先访问距离近的节点，第一次抵达任意节点时的路径长度就是最短路径长度。DFS 的本质是沿一条路径尽头探索后再回溯，天然适合"存不存在一条路径"或"遍历所有节点"的问题。两者共同点是：都需要 visited 集合防止重复访问，保证每个节点最多被访问一次，总复杂度 O(V + E)。
暴力 → 优化的推导路径¶
暴力是从起点枚举所有可能路径（指数级）。BFS/DFS 的改进是通过 visited 数组剪掉已访问节点，把指数复杂度压缩为线性。本质上是把"路径枚举"变成"状态枚举"：每个节点只代表一个状态，访问过就标记，不再重复。
代表题：岛屿数量（LeetCode 200）¶
二维网格中 '1' 表示陆地，'0' 表示水，计算岛屿数量。
题眼是"连通分量""网格遍历"。遍历每个未访问的陆地格，用 DFS 把整个连通的岛屿标记为已访问，每次触发 DFS 就是发现了一个新岛屿，计数加一。总复杂度 O(mn)，每个格子最多被访问一次。
def numIslands(grid):
m, n = len(grid), len(grid[0])
def dfs(i, j):
if not (0 <= i < m and 0 <= j < n) or grid[i][j] != '1':
return
grid[i][j] = '0' # 标记已访问（原地修改）
for di, dj in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(i+di, j+dj)
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count
跨算法的统一视角：增量维护¶
读完以上所有算法，可以发现一条贯穿始终的主线：与其每次从头重新计算，不如在上一次结果的基础上只处理变化的部分。
前缀和是对"历史累积和"的增量维护；差分是对"区间修改"的增量维护；单调队列是对"窗口极值"的增量维护；单调栈是对"最近更大元素"的增量维护；并查集是对"连通性"的增量维护；动态规划是对"子问题最优值"的增量维护。理解了这条主线，你就不是在学十几种独立的算法，而是在学一种思想在不同场景下的实例化。
每当遇到新题，先问自己：这个问题的"从头重算"代价是多少？变化量是什么？变化量有什么规律可以利用？ 能回答这三个问题，优化方向就自然浮现了。