C# 算法模式：面试与竞赛

五种完全不需要额外内存的模式，只用两个整数和题目给你的数组。讲清每种模式什么时候适用、为什么是线性的，以及最后一种里几乎人人都会写反的那一行。

双指针朝同一个方向走，两者之间的间隔就是答案。本文讲四种滑动窗口，再加一个计数技巧：“恰好 K 个”没法直接滑动，就把它变成一次减法。

预处理一次，之后每个区间查询都是常数时间。还有一个几乎没人教的反向技巧：只写两个格子，就能给整个区间做一次更新。

在有序数组里找一个值，是二分查找最没用的用法。真正重要的模式搜索的是一个从没被构建出来的答案空间，根本不需要有序数组。

一个不肯留下无用元素的栈，一趟扫描就能回答整个数组里每个元素的“下一个更大元素”是谁。同样的结构还能求出柱状图中最大的矩形。

计数时怎样避免每个元素查两次哈希表，Array.Sort 从哪个输入规模开始不再保持相等元素的原有顺序，以及 C# 直到 .NET 6 才有的堆，很多老的 C# 竞赛代码至今还在绕开它。

大多数 C# 题解存图的方式，正是它们超时的原因。接着讲广度优先搜索、不靠调用栈的深度优先搜索，以及顺带就能检测环的拓扑排序。

边一旦带权，BFS 就不再正确。Dijkstra 能解决；C# 的 PriorityQueue 没有 DecreaseKey，只能重复入队。如果每条边的权重都是 0 或 1，堆其实纯属多余。

不讲理论，只讲反复出现的五种动态规划模式，外加一个循环方向：写反了，其中一种模式就会悄悄变成另一个完全不同的问题。

正确的解法已经超时，你才会在意的那部分：不分配内存地读取输入，C# 不会提醒你的溢出，以及循环里的 Console.WriteLine 为什么要写 400,000 次。

C# 没有这类题默认的单链表节点类型，LinkedList 也不是。五个模式：一次遍历找中点、Floyd 环检测及其证明、原地反转，以及让特殊情况直接消失的哑节点。

三种递归遍历顺序只差一行代码；迭代写法为什么一紧张就写不出来；层序遍历靠的不是技巧，而是一个局部变量。

几乎所有树的题目都归结为一个问题：这个量是沿着树向下传，还是向上返回？路径和、不经过根的直径、最近公共祖先，以及人人第一次都会写错的二叉搜索树校验。

区间类问题全看一个选择：按起点排序，还是按终点排序。合并区间要前者，调度的贪心要后者，而两种写法的代码几乎一模一样。

一个模板，五道题。选择、探索、撤销选择——大家漏掉的往往是撤销选择，因为少了它，代码看起来也像写完了。

用异或找出只出现一次的值，用上大多数 C# 代码从没碰过的 BitOperations 类，再看看移位次数被悄悄取模、结果什么都没移的那个坑。