面试常见算法：识别思路、复杂度与 C# 模板
算法面试考查的不只是能否写出代码，还包括能否澄清条件、从朴素解法中发现瓶颈、说明优化依据，并准确分析时间与空间复杂度。只背题目答案通常很难迁移：题目稍微改变输入形式或约束，原来的代码就不再适用。
更稳定的复习方式是记住一组解题模式。看到“有序”“连续区间”“重复状态”“最少步数”等信号时，先缩小候选算法，再用不变量或状态定义验证选择是否正确。本文用 C# 整理常见模式，代码以容易在面试现场复现为目标，不追求技巧性最短写法。
1. 🧭 面试中的解题顺序
拿到题目后，可以按下面的顺序推进：
- 澄清输入：数据规模多大，是否有序，是否包含重复值、负数或空输入，能否修改原数据。
- 确认输出：要返回值、索引、数量、路径，还是只判断是否存在；无解时返回什么。
- 给出朴素解法：先保证正确，再指出重复计算、重复扫描或多余搜索在哪里。
- 识别结构：题目是否具有有序性、连续性、单调性、无后效性或重复子问题。
- 说明正确性：解释循环不变量、搜索空间为何能缩小，或状态转移为何覆盖所有选择。
- 验证边界：空集合、单元素、全部相同、答案不存在、整数溢出和递归深度。
- 分析复杂度：以实际代码为准，同时说明额外空间是否包含返回结果。
1.1 常见复杂度的直觉
| 复杂度 | 常见来源 | 面试中的判断 |
|---|---|---|
| O(1) | 数组索引、哈希表平均查询 | 输入增长时操作次数基本不变 |
| O(log n) | 二分查找、平衡树操作 | 每一步排除固定比例的数据 |
| O(n) | 单次扫描、哈希预处理 | 每个元素只处理常数次 |
| O(n log n) | 高效比较排序、分治 | 通常可以接受中等规模输入 |
| O(n²) | 两层枚举、比较所有元素对 | 数据量较大时需要寻找结构性优化 |
| O(2ⁿ)、O(n!) | 子集、排列等穷举搜索 | 必须依赖较小输入、剪枝或状态压缩 |
大 O 描述的是增长趋势，不是精确运行时间。哈希查询的 O(1) 通常指平均复杂度，排序的 O(n log n) 也不表示所有排序算法和输入都具有相同成本。回答时应把结论和具体实现绑定起来。
2. 🔑 哈希表：用空间换查询时间
识别信号： 题目需要快速判断元素是否出现、统计频次、去重，或建立“值到索引”的映射。朴素解法中如果存在“对每个元素再扫描一次寻找匹配项”，通常可以考虑哈希表。
核心思路： 扫描到当前位置时，哈希表保存已经处理过的信息。查找当前元素需要的互补值，就能把两层枚举压缩成一次扫描。
下面是一遍扫描的两数之和模板：
static int[] TwoSum(int[] numbers, int target)
{
var indexByValue = new Dictionary<int, int>();
for (int i = 0; i < numbers.Length; i++)
{
int complement = target - numbers[i];
if (indexByValue.TryGetValue(complement, out int otherIndex))
{
return new[] { otherIndex, i };
}
indexByValue[numbers[i]] = i;
}
return Array.Empty<int>();
}先查询、后写入很重要。这样不会把当前元素与自身重复使用，同时仍能正确处理两个值相同的情况，例如 [3, 3] 和目标值 6。
复杂度： 平均时间 O(n)，额外空间 O(n)。发生大量哈希冲突时，操作成本可能退化，因此 O(1) 查询不是无条件保证。
常见错误：
- 只用
HashSet<int>记录出现过的值，却忘记题目要求返回原始索引。 - 使用
Add保存重复键导致异常，而题目本身允许重复元素。 - 对可变对象计算哈希后又修改参与相等比较的字段，导致集合无法正确找到该键。
常见追问： 如果不允许额外 O(n) 空间，可以先排序再使用双指针，把额外空间降低到取决于排序实现的水平，但原始索引需要额外保存，时间复杂度也会变成 O(n log n)。
3. ↔️ 双指针：利用顺序缩小搜索空间
识别信号： 输入已经有序，或者题目要求原地处理数组；需要寻找元素对、删除重复项、合并区间，或判断链表是否存在环。
双指针常见两种形式：
- 相向指针：从左右两端开始，根据当前结果排除一侧。
- 同向指针：快指针负责扫描，慢指针维护已经处理好的区域。
下面在有序数组中判断是否存在和为目标值的元素对：
static bool HasPairWithSum(int[] sortedNumbers, int target)
{
int left = 0;
int right = sortedNumbers.Length - 1;
while (left < right)
{
long sum = (long)sortedNumbers[left] + sortedNumbers[right];
if (sum == target)
{
return true;
}
if (sum < target)
{
left++;
}
else
{
right--;
}
}
return false;
}这里的不变量是：当前答案如果存在，一定位于闭区间 [left, right]。由于数组有序，当两端之和偏小时，保留较小的左端点不可能与区间内其他元素得到更大的和，因此可以安全移动 left；偏大时同理移动 right。
复杂度： 时间 O(n)，额外空间 O(1)。如果输入尚未排序且允许排序，总时间通常为 O(n log n)。
常见错误：
- 在无序数组上直接根据和的大小移动指针，此时没有顺序依据，可能跳过答案。
- 循环写成
left <= right，让同一个元素被使用两次。 - 两个
int相加后才转换为long，整数可能已经溢出。应在加法前转换其中一个操作数。
常见追问： 如果要求保留原始索引，排序时需要把值和索引一起保存；如果要求原地删除重复项，则可以改用同向快慢指针维护有效前缀。
4. 🪟 滑动窗口：维护连续区间
识别信号： 题目讨论连续子数组或子串，并要求最长、最短、固定长度统计，或者满足某种频次和约束的区间。
核心思路： 右边界负责把新元素加入窗口，左边界在窗口不满足条件时向右收缩。关键不是“有两个指针”，而是窗口状态能够随着边界移动进行增量更新，不必每次重新扫描整个区间。
下面求不含重复字符的最长子串长度：
static int LengthOfLongestUniqueSubstring(string text)
{
var lastIndex = new Dictionary<char, int>();
int left = 0;
int best = 0;
for (int right = 0; right < text.Length; right++)
{
char current = text[right];
if (lastIndex.TryGetValue(current, out int previous))
{
left = Math.Max(left, previous + 1);
}
lastIndex[current] = right;
best = Math.Max(best, right - left + 1);
}
return best;
}窗口 [left, right] 始终不包含重复字符。left 只能向右移动，不能因为遇到较早位置的重复字符而后退，所以需要使用 Math.Max。
复杂度： 时间 O(n)，额外空间 O(k)，其中 k 是窗口内可能出现的字符种类数。
常见错误：
- 更新答案时忘记窗口长度是
right - left + 1。 - 删除或覆盖频次后没有正确判断窗口是否重新满足条件。
- 把所有连续区间问题都套用滑动窗口。比如寻找“和至少为目标值的最短子数组”时，若数组包含负数，加入新元素后窗口和不再单调变化，简单的左右收缩策略可能失效。
常见追问： 固定长度窗口不需要 while 收缩，只需在加入右端元素后移除离开窗口的左端元素；涉及多种字符频次时，可以维护 valid 计数，避免每次比较完整字典。
5. 🔍 二分查找：在单调空间中排除一半
识别信号： 数据有序，或者存在一个单调判断条件：当某个值可行时，更大或更小的一整侧也必然可行。后者常用于“最小可行值”“最大允许值”等答案空间搜索。
核心思路： 每次通过中点判断，确定答案只能位于哪一半。写二分查找时必须先明确区间含义，以及循环结束后返回的变量代表什么。
下面使用闭区间 [left, right] 查找第一个大于等于目标值的位置；不存在时返回数组长度：
static int LowerBound(int[] sortedNumbers, int target)
{
int left = 0;
int right = sortedNumbers.Length - 1;
int answer = sortedNumbers.Length;
while (left <= right)
{
int middle = left + (right - left) / 2;
if (sortedNumbers[middle] >= target)
{
answer = middle;
right = middle - 1;
}
else
{
left = middle + 1;
}
}
return answer;
}当 sortedNumbers[middle] >= target 时，中点可能是答案，但左侧还可能存在更早的位置，因此先记录中点，再继续搜索左半区间。
复杂度： 时间 O(log n)，额外空间 O(1)。
常见错误：
- 循环使用
left <= right，却只把边界更新为middle，导致区间不缩小并进入死循环。 - 找到一个目标值就立即返回，忽略题目要求第一个或最后一个位置。
- 在答案空间二分中没有证明判定函数具有单调性。
常见追问： “最小化最大值”类题目经常可以二分答案。此时数组不一定有序，但“给定上限是否可行”的布尔结果必须随候选值单调变化。
6. 📚 栈、队列与单调结构
识别信号：
- 最近加入的状态最先处理、括号配对、撤销操作：栈。
- 按到达顺序或按层扩展：队列。
- 查找左侧或右侧第一个更大、更小元素：单调栈。
单调栈保存尚未找到答案的元素索引，并维持栈内值的单调关系。
下面求每个位置右侧第一个更大元素的索引，不存在时保留 -1：
static int[] NextGreaterIndexes(int[] numbers)
{
int[] answer = new int[numbers.Length];
Array.Fill(answer, -1);
var stack = new Stack<int>();
for (int i = 0; i < numbers.Length; i++)
{
while (stack.Count > 0 && numbers[i] > numbers[stack.Peek()])
{
int index = stack.Pop();
answer[index] = i;
}
stack.Push(i);
}
return answer;
}栈中保存的是索引，因为答案通常需要位置或距离。每个索引最多入栈一次、出栈一次，虽然代码存在嵌套循环，总操作次数仍然是线性的。
复杂度： 时间 O(n)，额外空间 O(n)。
常见错误：
- 只看到嵌套
while就判断复杂度为 O(n²)，没有分析每个元素的总入栈和出栈次数。 - 混淆“严格更大”和“大于等于”，导致重复值处理错误。
- 使用
List<T>.RemoveAt(0)模拟队列，使每次出队都移动后续元素。C# 中应使用Queue<T>。
常见追问： 如果要求下一个更大元素的距离，可以保存 i - index；处理循环数组时，可以遍历两倍长度并用取模访问，但只在第一轮压入索引。
7. 🌲 DFS 与 BFS：系统遍历状态空间
识别信号： 输入天然构成树、图、网格或状态转换关系，需要判断连通性、遍历全部节点、查找路径，或者计算无权图中的最少步数。
- **DFS（深度优先搜索）**沿一条路径尽量深入，再返回处理其他分支，适合连通性、子树计算和需要回溯的搜索。
- **BFS（广度优先搜索）**按距离逐层扩展。在每条边代价相同的无权图中，节点第一次被访问时的层数就是最短步数。
下面给出邻接表上的 DFS 和 BFS 距离模板：
static void Dfs(int node, List<int>[] graph, bool[] visited)
{
if (visited[node])
{
return;
}
visited[node] = true;
foreach (int next in graph[node])
{
Dfs(next, graph, visited);
}
}
static int[] BfsDistances(int start, List<int>[] graph)
{
int[] distance = new int[graph.Length];
Array.Fill(distance, -1);
var queue = new Queue<int>();
queue.Enqueue(start);
distance[start] = 0;
while (queue.Count > 0)
{
int node = queue.Dequeue();
foreach (int next in graph[node])
{
if (distance[next] != -1)
{
continue;
}
distance[next] = distance[node] + 1;
queue.Enqueue(next);
}
}
return distance;
}访问标记应在节点入队时设置，而不是出队时设置，否则同一节点可能被多个前驱重复加入队列。
复杂度： 使用邻接表时，DFS 和 BFS 的时间都是 O(V + E)，额外空间为 O(V)，其中 V 是节点数，E 是边数。递归 DFS 的调用栈也要计入空间。
常见错误：
- 在可能有环的图中不记录访问状态，导致无限遍历。
- 把树的“父子关系天然无环”假设直接带到一般图。
- 声称 BFS 能解决所有最短路径问题。只有边权相同或视为无权时，普通 BFS 才直接得到最短步数。
- 在节点很多或路径很深时使用递归 DFS，没有考虑栈溢出风险。
常见追问： 网格搜索可以把每个坐标视为节点，通过方向数组生成相邻位置；如果所有边权为 0 或 1，可以进一步讨论 0-1 BFS，但它已超出普通队列 BFS 的模板范围。
8. 🧩 回溯：枚举选择并恢复现场
识别信号： 题目要求列出所有排列、组合、子集或满足约束的方案，输入规模较小，答案本身可能呈指数增长。
回溯可以抽象成三个动作：做选择、递归探索、撤销选择。递归参数描述当前搜索位置，路径保存已经做出的选择，剪枝排除不可能完成的分支。
下面生成从 1..n 中选择 k 个数的全部组合：
static List<List<int>> Combine(int n, int k)
{
var result = new List<List<int>>();
var path = new List<int>();
void Search(int start)
{
if (path.Count == k)
{
result.Add(new List<int>(path));
return;
}
int remaining = k - path.Count;
int lastStart = n - remaining + 1;
for (int value = start; value <= lastStart; value++)
{
path.Add(value);
Search(value + 1);
path.RemoveAt(path.Count - 1);
}
}
if (k >= 0 && k <= n)
{
Search(1);
}
return result;
}结果中必须使用 new List<int>(path) 保存路径副本。如果直接保存同一个 path 引用，后续撤销操作会改变已经加入结果的内容。
复杂度： 生成组合的输出规模为 C(n, k)，复制每个长度为 k 的结果需要 O(k)，因此时间可写为 O(C(n, k) × k)。不计算返回结果时，递归路径空间为 O(k)。
常见错误：
- 递归返回后忘记撤销选择，使不同分支共享错误状态。
- 排列问题没有使用
used数组，导致同一元素被重复选择。 - 输入含重复值时只排序却没有在同一递归层跳过重复候选。
- 只说“剪枝后很快”，却不说明最坏情况仍可能是指数级。
常见追问： 组合使用递增的 start 避免顺序不同但元素相同的重复结果；排列通常从所有未使用元素中选择，状态和去重规则不同。
9. 🎯 贪心：做出可证明的局部选择
识别信号： 题目要求最大数量、最少资源或最优安排，并且做出当前选择后，可以证明某个最优解仍然存在，不需要回头修改之前的决定。
“每次选当前看起来最好”只是策略描述，不是正确性证明。贪心通常需要交换论证：证明任意最优解都可以把它的第一个选择替换成贪心选择，且结果不会变差。
下面选择最多数量的互不重叠半开区间 [Start, End)：
static int MaxNonOverlappingIntervals((int Start, int End)[] intervals)
{
Array.Sort(intervals, (a, b) => a.End.CompareTo(b.End));
int count = 0;
int previousEnd = int.MinValue;
foreach ((int Start, int End) interval in intervals)
{
if (interval.Start < previousEnd)
{
continue;
}
count++;
previousEnd = interval.End;
}
return count;
}优先选择结束最早的区间，会为后续区间留下不小于其他选择的可用空间。任意最优方案的第一个区间都可以替换为结束更早的区间，而不会减少后续可选数量。
复杂度： 排序时间 O(n log n)，扫描时间 O(n)。额外空间取决于运行库排序实现；代码还会修改输入数组的顺序。
常见错误：
- 凭直觉选择最短区间或最早开始区间，却没有证明该规则不会破坏全局最优。
- 忽略区间是闭区间还是半开区间，导致端点相接时的判断不同。
- 题目要求输出具体方案，却只记录数量。
常见追问： 如果局部选择会影响后续状态，且无法通过交换论证保证最优，通常需要考虑动态规划；如果区间带权重，“结束最早”也不再直接保证总权重最大。
10. 🧠 动态规划：复用重复子问题
识别信号： 问题包含重复子问题，需要求最大值、最小值、方案数或可行性；当前决策依赖有限的历史状态，并且最优解能够由规模更小的最优解构成。
写动态规划前先回答五个问题：
dp[i]或当前变量表示什么。- 当前状态可以从哪些旧状态转移而来。
- 初始状态是什么。
- 状态必须按什么顺序计算。
- 最终答案位于哪个状态。
下面求不能选择相邻元素时的最大元素和。允许一个元素都不选，因此全为负数时返回 0：
static int MaxNonAdjacentSum(int[] numbers)
{
int bestBeforePrevious = 0;
int bestBeforeCurrent = 0;
foreach (int number in numbers)
{
int skipCurrent = bestBeforeCurrent;
int takeCurrent = bestBeforePrevious + number;
int current = Math.Max(skipCurrent, takeCurrent);
bestBeforePrevious = bestBeforeCurrent;
bestBeforeCurrent = current;
}
return bestBeforeCurrent;
}状态定义为“处理完当前位置之前的元素后，能够取得的最大和”。对当前元素只有两种互斥选择：跳过它，答案保持为前一个状态；选择它，就只能加到隔一个位置之前的最优结果上。
复杂度： 时间 O(n)，额外空间 O(1)。如果需要恢复具体选择了哪些元素，则通常要保存完整状态或额外的决策信息。
常见错误：
- 没有先定义状态含义，直接凭样例猜转移公式。
- 一维状态压缩时过早覆盖仍会被后续计算使用的旧值。
- 初始化只适用于正数输入，却没有确认题目是否允许负数或空选择。
- 把所有最优化问题都归为动态规划，没有检查状态数量是否可接受。
常见追问： 自顶向下记忆化搜索和自底向上动态规划通常解决同一组状态。前者更接近递归定义并可能只访问必要状态，后者避免递归调用并更容易做空间压缩。
11. 📋 算法选择速查表
| 题目特征 | 优先考虑 | 必要前提或检查点 |
|---|---|---|
| 快速判断存在、计数、去重 | 哈希表 | 接受额外空间；明确键和相等语义 |
| 有序数组中寻找元素对 | 相向双指针 | 移动指针必须有有序性依据 |
| 原地压缩、去重、分区 | 同向双指针 | 慢指针维护已处理区域 |
| 连续子数组或子串的最长、最短 | 滑动窗口 | 窗口条件能随边界增量维护 |
| 有序数据查找边界 | 二分查找 | 明确区间定义和目标边界 |
| 最小可行值、最大允许值 | 答案空间二分 | 判定结果随候选值单调变化 |
| 最近未匹配状态、括号、撤销 | 栈 | 后进先出的处理顺序 |
| 右侧第一个更大或更小元素 | 单调栈 | 明确严格或非严格比较 |
| 树、图、网格的连通性 | DFS 或 BFS | 一般图需要访问标记 |
| 无权图最少步数 | BFS | 每条边代价相同 |
| 枚举排列、组合、子集 | 回溯 | 输入规模允许指数级搜索 |
| 区间安排等局部选择问题 | 贪心 | 必须能证明局部选择不损失最优性 |
| 重复子问题的最值、计数、可行性 | 动态规划 | 状态和转移规模可接受 |
同一道题可能有多种解法。例如两数之和可以使用哈希表，也可以在排序后使用双指针。面试中不必假装只有一个答案，而应根据是否允许修改输入、是否需要原始索引、空间限制和数据规模解释取舍。
12. 复习顺序与临场检查
建议按依赖关系复习，而不是从困难题目开始随机刷题：
- 先熟悉数组、字符串、链表以及 O(1)、O(n)、O(log n)、O(n log n) 的判断。
- 掌握哈希表和双指针，练习把 O(n²) 朴素解法优化为 O(n) 或 O(n log n)。
- 掌握滑动窗口与二分边界，重点检查循环不变量和索引更新。
- 掌握栈、队列、树与图的 DFS/BFS，形成统一的访问状态模板。
- 再学习回溯，明确路径、选择列表、终止条件和撤销动作。
- 最后集中训练贪心证明和动态规划状态设计，避免只记结论或代码。
提交答案前，可以快速检查：空输入是否处理、循环是否必然推进、数组索引是否越界、重复值语义是否正确、整数是否可能溢出、递归是否可能过深，以及复杂度是否和实际实现一致。
真正需要记住的不是每道题的完整代码，而是模板背后的依据：哈希表保存什么信息，指针为什么可以移动，窗口为什么可以收缩，二分为什么能够排除一半，DFS/BFS 如何避免重复访问，回溯如何恢复状态，贪心如何证明，动态规划的状态又代表什么。能把这些问题说明白，代码通常只是最后一步。