五种完全不需要额外内存的模式，只用两个整数和题目给你的数组。讲清每种模式什么时候适用、为什么是线性的，以及最后一种里几乎人人都会写反的那一行。
竞赛题考的是你能多快认出题目的“形状”。双指针是第一个值得学的形状，因为它几乎不花任何代价：不用第二个数组，不用字典，不用递归。只要两个 int 变量，加上题目给你的数组。
本篇是十六篇中的第 1 篇，每篇讲五个模式。下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果里粘贴过来。
怎么运行
.NET 10 可以直接运行单个 .cs 文件，不需要项目，不需要类，也不需要 Main：
dotnet run twopointers.cs这是新功能，也是动手试这些代码最快的方式。本页的代码全都按这种方式写。
模式 1 — 从两端向中间收拢
给你一个有序数组，找出和为目标值的两个数。
最直接的写法是枚举每一对。六个元素的数组这样做没问题。但数一数它实际做了多少事：
int[] a = [2, 7, 11, 15, 19, 26];
int target = 30;
int bruteSteps = 0;
for (int i = 0; i < a.Length; i++)
for (int j = i + 1; j < a.Length; j++)
{
bruteSteps++;
if (a[i] + a[j] == target) goto done;
}
done:
int twoPtrSteps = 0;
int lo = 0, hi = a.Length - 1;
while (lo < hi)
{
twoPtrSteps++;
int sum = a[lo] + a[hi];
if (sum == target) break;
if (sum < target) lo++; else hi--;
}
Console.WriteLine($"n = {a.Length}");
Console.WriteLine($"every pair : {bruteSteps} pairs examined");
Console.WriteLine($"two pointers : {twoPtrSteps} steps");输出：
n = 6
every pair : 11 pairs examined
two pointers : 4 steps11 对和 4 步，差距看起来不大。可到了 n = 100000，就是五十亿对和十万步，竞赛的输赢全在这里。
关键一步是这样的。数组有序，所以 a[hi] 是剩下的数里最大的。如果 a[lo] + a[hi] 太小，那 a[lo] 在哪儿都找不到搭档：你刚把它和能用的最大值配了对，还是不够。所以 a[lo] 不可能出现在任何答案里。把它扔掉，以后再也不看。
反过来也一样：如果和太大，a[hi] 跟剩下的任何数配对都太大，把它丢掉。
双指针从有序数组的两端向中间收拢。变灰的格子已经被排除，之后再也不会看。
int[] a = [2, 7, 11, 15, 19, 26];
int target = 30;
int lo = 0, hi = a.Length - 1;
while (lo < hi)
{
int sum = a[lo] + a[hi];
string move = sum == target ? "= target, stop"
: sum < target ? "< target, lo++"
: "> target, hi--";
Console.WriteLine($"lo={lo} hi={hi} {a[lo],2} + {a[hi],2} = {sum,2} {move}");
if (sum == target) break;
if (sum < target) lo++; else hi--;
}
Console.WriteLine($"\nindices ({lo}, {hi}) -> values ({a[lo]}, {a[hi]})");输出：
lo=0 hi=5 2 + 26 = 28 < target, lo++
lo=1 hi=5 7 + 26 = 33 > target, hi--
lo=1 hi=4 7 + 19 = 26 < target, lo++
lo=2 hi=4 11 + 19 = 30 = target, stop
indices (2, 4) -> values (11, 19)每一步恰好排除一个索引，而且永远不会回头再考虑它。一共 n 个索引，所以最多 n 步。这就是它线性的原因。值得用这种方式来说，而不是说“两个指针在中间相遇”：排除才是原因，相遇只是表面看起来的样子。
代价： 排序之后 O(n) 时间，O(1) 空间。
适用场景： 输入有序，或者你排得起序，并且 lo 右移会让你关心的量变大、hi 左移会让它变小。这种单调性就是全部前提。没有它，排除那一步就不成立，整个算法会悄无声息地返回错误答案。
模式 2 — 写指针
原地删除有序数组中的重复项，并返回剩下多少个值。
容易想到的写法是建一个 List<int>，把要保留的值加进去，再拷回原数组。结果是对的，但它多分配了一个数组。到了 10⁶ 个元素，这次分配就决定了能不能通过。
这里两个指针朝同一个方向走。r 读取每一个格子，w 标出下一个保留值该写到哪里。之所以不会破坏任何数据，是因为 w 永远追不上 r：w 只在 r 前进时才前进，而且起点就在 r 后面。
一个数组，两份工作。r 读取每一个格子，w 标出下一个保留值该写到哪里。w 永远不会超过 r，所以没有哪个值在被读取之前就被覆盖。最后 w 之后的部分都是残留数据，直接忽略。
int[] a = [1, 1, 2, 2, 2, 3, 4, 4, 5];
Console.WriteLine($"before: [{string.Join(", ", a)}]\n");
int w = 1;
for (int r = 1; r < a.Length; r++)
{
if (a[r] == a[w - 1])
{
Console.WriteLine($"r={r} a[r]={a[r]} {$"same as a[{w - 1}]",-12} skip w stays {w}");
continue;
}
a[w] = a[r];
w++;
Console.WriteLine($"r={r} a[r]={a[r]} {"new value",-12} a[{w - 1}]={a[r]} w -> {w}");
}
Console.WriteLine($"\nkept {w}: [{string.Join(", ", a[..w])}]");
Console.WriteLine($"tail : [{string.Join(", ", a[w..])}] <- stale, and that is fine");输出：
before: [1, 1, 2, 2, 2, 3, 4, 4, 5]
r=1 a[r]=1 same as a[0] skip w stays 1
r=2 a[r]=2 new value a[1]=2 w -> 2
r=3 a[r]=2 same as a[1] skip w stays 2
r=4 a[r]=2 same as a[1] skip w stays 2
r=5 a[r]=3 new value a[2]=3 w -> 3
r=6 a[r]=4 new value a[3]=4 w -> 4
r=7 a[r]=4 same as a[3] skip w stays 4
r=8 a[r]=5 new value a[4]=5 w -> 5
kept 5: [1, 2, 3, 4, 5]
tail : [3, 4, 4, 5] <- stale, and that is fine看看尾部。[3, 4, 4, 5] 就留在那里，是残留数据。这不是需要清理的 bug：把它覆盖掉要再多走一遍，却没有任何好处。约定是答案为 a[..w]，w 之后的内容与调用方无关。
代价： O(n) 时间，O(1) 空间。
适用场景： 题目说原地、返回新长度或者不要分配额外空间。压缩、过滤、按条件划分，都是这个模式换了个说法。
模式 3 — 排序、固定锚点、扫描
找出所有和为零的三元组，同一个三元组不能重复输出。
三层循环是 O(n³)，过不了。但固定第一个值，再看剩下的问题：找两个数，和为 -a[i]。这正是模式 1。开头排一次序花 O(n log n)，换来模式 1 需要的单调性。
真正麻烦的不是查找，而是重复。重复要在两个不同的地方跳过，原因也各不相同：
- 锚点重复。 如果
a[i] == a[i-1]，以i开头的三元组在i-1时已经全部找到了。整个锚点直接跳过。 - 命中后
lo或hi重复。 记下一个三元组之后，要让两个指针都走过刚用过的值的所有副本，否则下一轮马上又会输出同一个三元组。
先排一次序，然后固定一个值，在剩下的部分上跑双指针。跳过重复的锚点，同一个三元组才不会被输出两次。
int[] a = [-1, 2, -4, -1, 1, 0];
Array.Sort(a);
Console.WriteLine($"sorted: [{string.Join(", ", a)}]\n");
List<(int, int, int)> found = [];
for (int i = 0; i < a.Length - 2; i++)
{
if (i > 0 && a[i] == a[i - 1])
{
Console.WriteLine($"anchor i={i} a[i]={a[i],2} duplicate anchor, skip");
continue;
}
int lo = i + 1, hi = a.Length - 1;
Console.WriteLine($"anchor i={i} a[i]={a[i],2} need a[lo] + a[hi] == {-a[i]}");
while (lo < hi)
{
int sum = a[i] + a[lo] + a[hi];
Console.WriteLine($" lo={lo} hi={hi} {a[i],2} + {a[lo],2} + {a[hi],2} = {sum,2}");
if (sum == 0)
{
found.Add((a[i], a[lo], a[hi]));
while (lo < hi && a[lo] == a[lo + 1]) lo++;
while (lo < hi && a[hi] == a[hi - 1]) hi--;
lo++; hi--;
}
else if (sum < 0) lo++;
else hi--;
}
}
Console.WriteLine();
foreach (var t in found) Console.WriteLine($"triplet: {t}");输出：
sorted: [-4, -1, -1, 0, 1, 2]
anchor i=0 a[i]=-4 need a[lo] + a[hi] == 4
lo=1 hi=5 -4 + -1 + 2 = -3
lo=2 hi=5 -4 + -1 + 2 = -3
lo=3 hi=5 -4 + 0 + 2 = -2
lo=4 hi=5 -4 + 1 + 2 = -1
anchor i=1 a[i]=-1 need a[lo] + a[hi] == 1
lo=2 hi=5 -1 + -1 + 2 = 0
lo=3 hi=4 -1 + 0 + 1 = 0
anchor i=2 a[i]=-1 duplicate anchor, skip
anchor i=3 a[i]= 0 need a[lo] + a[hi] == 0
lo=4 hi=5 0 + 1 + 2 = 3
triplet: (-1, -1, 2)
triplet: (-1, 0, 1)i=2 处的锚点一步内层循环都没跑就被跳过了，因为 -1 在 i=1 时已经轮过一次。正是这次跳过，让输出成为一个集合，而不是带重复项的列表。
代价： O(n²) 时间（n 个锚点，每个做一次线性扫描），再加上排序。除输出外 O(1) 空间。
适用场景： 要找满足某个条件的固定大小组合。四数之和就是在外面再套一层循环。
模式 4 — 把每个值送回自己的索引
数组里有 n 个值，取值范围是 1..n。有一个值出现了两次，有一个值缺失。不用额外内存，把两个都找出来。
用 HashSet<int> 可以解，但要 O(n) 内存。求和的技巧只能给你一个方程，而你需要两个。再看一遍约束：值是 1..n，数组长度是 n。数组本身就是一张哈希表，哈希函数是 v - 1。
所以把每个值放到它该在的位置。值 3 放到索引 2。如果两个值要抢同一个位置，数组就再也挪不动了，而那个始终没被填上的格子会告诉你缺的是哪个数。
循环用的是 while 而不是 for，这一点很重要。交换之后，索引 i 上换来了一个还没归位的值，所以 i 不能前进。只有 i 上的值已经归位，i 才前进。
循环排序把每个值送到它该在的索引。两个值要抢同一个位置时，数组就不再移动，剩下没归位的那个值同时指出了重复的数和缺失的数。
int[] a = [3, 1, 5, 4, 3, 2];
Console.WriteLine($"start: [{string.Join(", ", a)}] values are 1..{a.Length}\n");
int i = 0;
while (i < a.Length)
{
int home = a[i] - 1;
if (a[i] != a[home])
{
Console.WriteLine($"i={i} a[i]={a[i]} belongs at index {home}, which holds {a[home]} swap");
(a[i], a[home]) = (a[home], a[i]);
Console.WriteLine($" -> [{string.Join(", ", a)}]");
}
else
{
Console.WriteLine($"i={i} a[i]={a[i]} is already home (or its twin is) i++");
i++;
}
}
Console.WriteLine($"\nsorted as far as it can be: [{string.Join(", ", a)}]\n");
for (int j = 0; j < a.Length; j++)
if (a[j] != j + 1)
Console.WriteLine($"index {j} holds {a[j]}, should hold {j + 1} -> duplicate = {a[j]}, missing = {j + 1}");输出：
start: [3, 1, 5, 4, 3, 2] values are 1..6
i=0 a[i]=3 belongs at index 2, which holds 5 swap
-> [5, 1, 3, 4, 3, 2]
i=0 a[i]=5 belongs at index 4, which holds 3 swap
-> [3, 1, 3, 4, 5, 2]
i=0 a[i]=3 is already home (or its twin is) i++
i=1 a[i]=1 belongs at index 0, which holds 3 swap
-> [1, 3, 3, 4, 5, 2]
i=1 a[i]=3 is already home (or its twin is) i++
i=2 a[i]=3 is already home (or its twin is) i++
i=3 a[i]=4 is already home (or its twin is) i++
i=4 a[i]=5 is already home (or its twin is) i++
i=5 a[i]=2 belongs at index 1, which holds 3 swap
-> [1, 2, 3, 4, 5, 3]
i=5 a[i]=3 is already home (or its twin is) i++
sorted as far as it can be: [1, 2, 3, 4, 5, 3]
index 5 holds 3, should hold 6 -> duplicate = 3, missing = 6这看起来可能是平方级的：循环里有交换，而且有时不前进。其实不是。每次交换至少把一个值放到它的最终位置，而归位的值再也不会被移动。一共 n 个值，所以整个运行过程中最多 n 次交换。
当值是某个已知范围的排列时，数组本身就是一张哈希表，你完全可以把它当哈希表用。
代价： O(n) 时间，O(1) 空间。
适用场景： 题目说值在 1 到 n 之间或在 0 到 n 之间，并且要找缺失或重复的数。这种措辞就是信号，题目写出来是在帮你。
模式 5 — 一趟分出三个区域
对只含 0、1、2 的数组排序。只扫一趟，不用基于比较的排序。
分别计数再重写也行，但要两趟。它也没法推广，这才是真正的问题。下面这个写法，就是在大量相等键的情况下围绕基准值做划分的方法，也正是它让快速排序在重复值很多的输入上不至于退化。
三个索引把数组分成四个区域。low 左边都是已经确定的 0，high 右边都是已经确定的 2。mid 到 high 之间是还没人看过的部分，每一轮缩小一个。
整个算法就是这三条规则加一个不变式：low 左边都是 0，high 右边都是 2，未知区域每一轮缩小一个。最后一条规则最容易写错 — 从 high 换回来的值从没被检查过，所以 mid 不能越过它。
第三条规则值得再读一遍，因为它最常被写错。把 a[mid] 和 a[high] 交换后，换到 mid 的值来自未检查的区域，还没人测过它。如果让 mid 越过它，你就把一个没测过的值塞进了已经确定的 1 区域。遇到 0 时让 mid 前进却没问题，原因正好相反：换过来的值来自 low，而 mid 之前的所有值都已经测过了。
int[] a = [2, 0, 2, 1, 1, 0, 2, 1, 0];
Console.WriteLine($"start: [{string.Join(", ", a)}]\n");
int low = 0, mid = 0, high = a.Length - 1;
while (mid <= high)
{
switch (a[mid])
{
case 0:
(a[low], a[mid]) = (a[mid], a[low]);
Console.WriteLine($"a[mid]=0 swap into the 0s low {low}->{low + 1} mid {mid}->{mid + 1} high {high} [{string.Join(", ", a)}]");
low++; mid++;
break;
case 1:
Console.WriteLine($"a[mid]=1 already correct low {low} mid {mid}->{mid + 1} high {high} [{string.Join(", ", a)}]");
mid++;
break;
default:
(a[mid], a[high]) = (a[high], a[mid]);
Console.WriteLine($"a[mid]=2 swap into the 2s low {low} mid {mid} high {high}->{high - 1} [{string.Join(", ", a)}]");
high--;
break;
}
}
Console.WriteLine($"\ndone: [{string.Join(", ", a)}]");输出：
start: [2, 0, 2, 1, 1, 0, 2, 1, 0]
a[mid]=2 swap into the 2s low 0 mid 0 high 8->7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=0 swap into the 0s low 0->1 mid 0->1 high 7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=0 swap into the 0s low 1->2 mid 1->2 high 7 [0, 0, 2, 1, 1, 0, 2, 1, 2]
a[mid]=2 swap into the 2s low 2 mid 2 high 7->6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 2->3 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 3->4 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=1 already correct low 2 mid 4->5 high 6 [0, 0, 1, 1, 1, 0, 2, 2, 2]
a[mid]=0 swap into the 0s low 2->3 mid 5->6 high 6 [0, 0, 0, 1, 1, 1, 2, 2, 2]
a[mid]=2 swap into the 2s low 3 mid 6 high 6->5 [0, 0, 0, 1, 1, 1, 2, 2, 2]
done: [0, 0, 0, 1, 1, 1, 2, 2, 2]九个值，九轮循环，而且从来没有拿两个数组元素互相比较。
代价： O(n) 时间，O(1) 空间，并且在这里真正重要的意义上是稳定的：一趟完成，没有递归。
适用场景： 需要按一个开销很小的判断把元素分成三组。经典说法是国旗的颜色（荷兰国旗问题），更有用的说法是 less than pivot、equal to pivot、greater than pivot。
要点
- 从两端收拢需要的是单调性，不只是有序。
lo右移必须把你关心的量往一个方向推，hi左移必须往另一个方向推。信任“排除”这一步之前，先确认这一点。 - 同向双指针就是原地修改。
w跟在r后面，所以没有哪个值在被读取之前就被覆盖；w之后的残留尾部是有意留下的。 - 锚点重复和指针重复是两种不同的去重 bug。 修好一个并不能修好另一个，而且小测试用例里只能看出其中一个。
- 题目里出现
1..n，意味着数组可以当自己的哈希表。 空间从 O(n) 降到 O(1)，而交换循环之所以是线性的，是因为每次交换都让一个值永久归位。 - 从
high换进来之后，mid保持不动。 刚换来的值从没被检查过。这里只差一个字符，却是整个模式里最常见的 bug。
第 2 篇沿用同样的双索引思路，但让两个指针朝同一个方向走，两者之间的间隔就是答案：滑动窗口，以及把“恰好 K 个”变成一次减法的“至多 K 个”技巧。