正确的解法已经超时，你才会在意的那部分：不分配内存地读取输入，C# 不会提醒你的溢出，以及循环里的 Console.WriteLine 为什么要写 400,000 次。
讲了九篇算法，最后才是这一篇。放在最后，是因为出事之前没人想看它：解法可以证明是对的，你写的测试全都通过，评测机却判了超时。
在 C# 里，原因往往不在算法。
下面每个程序都是完整的，都在 .NET 10 上跑过，输出直接从运行结果粘贴过来。如果某个数字是耗时而不是计数，它来自一台机器上的一次运行，看的是比例，不是具体数值。
模式 46 — 读取输入
在循环里调用 Console.ReadLine()，是正确的 C# 解法跑得太慢最常见的原因。它要经过加了同步的 TextReader，每读一行就生成一个 string 对象。接着 Split(' ') 又给每个 token 生成一个字符串。
读取 300,000 个整数的三种写法：
Span<T> 就是一个指针加一个长度，指向已经存在的内存。对它切片只是算术；用同样的 [a..b] 语法对数组切片，却会分配内存并复制。
using System.Text;
// A deterministic input: 300,000 numbers on one line, built in memory so this
// program is self-contained.
var rng = new Random(7);
var sb = new StringBuilder();
int n = 300_000;
for (int i = 0; i < n; i++) { if (i > 0) sb.Append(' '); sb.Append(rng.Next(1, 1_000_000_000)); }
string line = sb.ToString();
byte[] bytes = Encoding.ASCII.GetBytes(line);
static long Measure(string name, Func<long> parse)
{
long before = GC.GetTotalAllocatedBytes(precise: true);
long sum = parse();
long allocated = GC.GetTotalAllocatedBytes(precise: true) - before;
Console.WriteLine($"{name,-22} sum={sum} allocated {allocated / 1024 / 1024,4} MB");
return sum;
}
// 1. What everyone writes. One string object per token.
long a = Measure("Split + int.Parse", () =>
{
long sum = 0;
foreach (string tok in line.Split(' ')) sum += int.Parse(tok);
return sum;
});
// 2. Same shape, but int.Parse accepts a ReadOnlySpan<char>, so no substrings.
long b = Measure("Span, no substrings", () =>
{
ReadOnlySpan<char> span = line;
long sum = 0;
foreach (Range r in span.Split(' ')) sum += int.Parse(span[r]);
return sum;
});
// 3. Read the bytes and build the number by hand. Nothing is allocated at all.
long c = Measure("bytes, hand-parsed", () =>
{
long sum = 0;
int i = 0;
while (i < bytes.Length)
{
while (i < bytes.Length && bytes[i] == ' ') i++;
int x = 0;
while (i < bytes.Length && bytes[i] >= '0' && bytes[i] <= '9') x = x * 10 + (bytes[i++] - '0');
sum += x;
}
return sum;
});
Console.WriteLine($"\nall three agree: {a == b && b == c}");输出：
Split + int.Parse sum=149553782500880 allocated 17 MB
Span, no substrings sum=149553782500880 allocated 0 MB
bytes, hand-parsed sum=149553782500880 allocated 0 MB
all three agree: True同样的工作，同样的答案，一边是 17 MB 垃圾，一边是零。
同一组对比在这台机器上的耗时：Split 约 55 ms，span 版本约 38 ms，手工解析字节约 17 ms。如果输入是每行一个数，用 Console.ReadLine 逐行读要约 40 ms，带缓冲读取只要 18 ms。
中间那种写法值得多看一眼，因为改起来几乎没有成本。int.Parse 从 .NET Core 2.1 起就接受 ReadOnlySpan<char>，而 MemoryExtensions.Split 产出的是 Range 值，不是字符串。把 string 换成 ReadOnlySpan<char>，再用 range 做索引，所有子串分配就都没了。
放进模板里的应该是字节读取那一版。它二十行，从不分配内存，也不在乎输入里的空白怎么排。
适用场景： 输入超过几千个 token。少于这个量，怎么清楚怎么写。
模式 47 — Span<T> 与 stackalloc
Span<T> 就是一个指针加一个长度。对它切片只是算术。用同样的 [a..b] 语法对数组切片，会分配一个新数组并复制。
stackalloc 在栈上放一块固定大小的小缓冲区。不分配堆内存，没有垃圾回收，方法返回时它就消失了。
// stackalloc puts a small array on the STACK. No allocation, no GC, and it
// disappears when the method returns. Bounded sizes only — this is not for
// anything that depends on input size.
static int LongestUniqueRun(string s)
{
Span<int> lastSeen = stackalloc int[128]; // ASCII, fixed size, no heap
lastSeen.Fill(-1);
int lo = 0, best = 0;
for (int r = 0; r < s.Length; r++)
{
int prev = lastSeen[s[r]];
if (prev >= lo) lo = prev + 1; // the guard from part 2
lastSeen[s[r]] = r;
best = Math.Max(best, r - lo + 1);
}
return best;
}
// A Span slice is a VIEW. No copy is made, so this allocates nothing at all.
static long SumOfHalves(int[] data)
{
ReadOnlySpan<int> all = data;
ReadOnlySpan<int> left = all[..(all.Length / 2)];
ReadOnlySpan<int> right = all[(all.Length / 2)..];
long a = 0, b = 0;
foreach (int x in left) a += x;
foreach (int x in right) b += x;
return a + b;
}
int[] data = [.. Enumerable.Range(1, 1_000_000)];
long before = GC.GetTotalAllocatedBytes(precise: true);
Console.WriteLine($"longest unique run in \"abcabcbb\": {LongestUniqueRun("abcabcbb")}");
Console.WriteLine($"longest unique run in \"abba\" : {LongestUniqueRun("abba")}");
Console.WriteLine($"sum via span slices : {SumOfHalves(data):N0}");
long after = GC.GetTotalAllocatedBytes(precise: true);
Console.WriteLine($"allocated by all of the above : {after - before} bytes");
// The array version of the same slicing DOES copy.
before = GC.GetTotalAllocatedBytes(precise: true);
int[] copy = data[..(data.Length / 2)];
after = GC.GetTotalAllocatedBytes(precise: true);
Console.WriteLine($"\nint[] range operator copies : {(after - before) / 1024 / 1024} MB for {copy.Length:N0} ints");
Console.WriteLine($"the same slice as a Span : 0 bytes — it is a pointer and a length");输出：
longest unique run in "abcabcbb": 3
longest unique run in "abba" : 2
sum via span slices : 500,000,500,000
allocated by all of the above : 8344 bytes
int[] range operator copies : 1 MB for 500,000 ints
the same slice as a Span : 0 bytes — it is a pointer and a length频率表是最日常的用法。一个函数被调用十万次，里面的 new int[128] 就是十万次分配；换成 stackalloc int[128]，一次都没有。
大小必须是很小的常量。栈空间默认大约 1MB，第 7 篇里限制递归深度的也是这点预算。对随输入规模增长的东西用 stackalloc，慢程序就会直接变成崩掉的程序。
再看最后两行。对 int[] 做 data[..500000]，复制了 1 MB。同样的表达式用在 ReadOnlySpan<int> 上，什么都没复制。语法一样，代价天差地别，而代码里看不出任何区别。
适用场景： 热点函数里需要一小块固定缓冲区，或者只切片、只读取。
模式 48 — 溢出
C# 的算术默认是 unchecked。溢出不抛异常，而是按规定的行为悄悄回绕。
C# 的算术默认是 unchecked。溢出不算错误，而是规定好的回绕行为 — 所以故障总在离肇事那一行很远的地方冒出来。
// 1. The classic binary-search overflow.
int lo = 2_000_000_000, hi = 2_100_000_000;
Console.WriteLine($"(lo + hi) / 2 = {(lo + hi) / 2} <- negative, and silently so");
Console.WriteLine($"lo + (hi - lo) / 2 = {lo + (hi - lo) / 2} <- correct");
// 2. Summing ints into an int.
int[] big = [.. Enumerable.Repeat(500_000_000, 6)];
int sumInt = 0;
foreach (int x in big) sumInt += x;
long sumLong = 0;
foreach (int x in big) sumLong += x;
Console.WriteLine($"\nsix values of 500,000,000");
Console.WriteLine($" into an int : {sumInt,20:N0}");
Console.WriteLine($" into a long : {sumLong,20:N0}");
// 3. C# does NOT check by default. It will if you ask.
try
{
checked { int bad = int.MaxValue; bad++; Console.WriteLine(bad); }
}
catch (OverflowException)
{
Console.WriteLine($"\nchecked { "{" } int.MaxValue + 1 { "}" } threw OverflowException");
}
int quiet = int.MaxValue;
unchecked { quiet++; }
Console.WriteLine($"unchecked int.MaxValue + 1 = {quiet} (this is the default)");
// 4. The limits, for reference.
Console.WriteLine($"\nint max {int.MaxValue,26:N0} about 2.1 x 10^9");
Console.WriteLine($"long max {long.MaxValue,26:N0} about 9.2 x 10^18");
Console.WriteLine($"\n1000 * 1000 * 1000 * 4 as int = {unchecked(1000 * 1000 * 1000 * 4)}");
Console.WriteLine($"1000L * 1000 * 1000 * 4 = {1000L * 1000 * 1000 * 4:N0}");输出：
(lo + hi) / 2 = -97483648 <- negative, and silently so
lo + (hi - lo) / 2 = 2050000000 <- correct
six values of 500,000,000
into an int : -1,294,967,296
into a long : 3,000,000,000
checked { int.MaxValue + 1 } threw OverflowException
unchecked int.MaxValue + 1 = -2147483648 (this is the default)
int max 2,147,483,647 about 2.1 x 10^9
long max 9,223,372,036,854,775,807 about 9.2 x 10^18
1000 * 1000 * 1000 * 4 as int = -294967296
1000L * 1000 * 1000 * 4 = 4,000,000,000从这段输出里可以得出三个习惯。
写 lo + (hi - lo) / 2。 第 4 篇里的每个二分查找都这么写。(lo + hi) / 2 在数值小的时候是对的，数值一大就得到负索引。
累加到 long 里。 六个数单独放进 int 都绰绰有余，加起来却放不下。要紧的是累加变量的类型，不是元素的类型。
先转换再相乘，不要乘完再转换。 (long)a * b 先把 a 扩成 64 位，乘法在 64 位里做。(long)(a * b) 在 int 里做乘法，先溢出，再把错误的结果扩宽。
经验法则：int 过了二十亿出头就不够用了。只要中间值有可能到这个量级（两个接近 10⁵ 的数相乘就已经到了），就用 long。在 64 位运行时上，这没有任何代价。
调试时 checked { } 很有用：溢出会在肇事的那一行报出来，而不是在下游某个地方。
模式 49 — 模运算
“对 10⁹+7 取模”的答案随处可见，因为真实的答案得用大整数库才装得下。
需要两样东西：不用做十亿次乘法的幂运算，以及除法，而除法在这里并不存在。
const long Mod = 1_000_000_007;
// Fast exponentiation: square the base, halve the exponent.
static long Power(long b, long e, long m)
{
long result = 1;
b %= m;
while (e > 0)
{
if ((e & 1) == 1) result = result * b % m;
b = b * b % m;
e >>= 1;
}
return result;
}
Console.WriteLine($"2^10 mod {Mod} = {Power(2, 10, Mod)}");
Console.WriteLine($"2^1000000 mod {Mod} = {Power(2, 1_000_000, Mod)}");
Console.WriteLine($"steps for e=1000000 : {(int)Math.Log2(1_000_000) + 1} squarings, not a million multiplications");
// Division does not exist mod p. Multiply by the modular inverse instead.
// Fermat: a^(p-1) = 1 mod p, so a^(p-2) is the inverse when p is prime.
static long Inverse(long a, long m) => Power(a, m - 2, m);
long inv3 = Inverse(3, Mod);
Console.WriteLine($"\ninverse of 3 = {inv3}");
Console.WriteLine($"3 * inverse(3) mod p = {3 * inv3 % Mod} <- 1, so it really is the inverse");
Console.WriteLine($"10 / 3 mod p = {10 * inv3 % Mod}");
Console.WriteLine($"check: that * 3 mod p = {10 * inv3 % Mod * 3 % Mod} <- back to 10");
// The trap: int arithmetic overflows BEFORE the modulus is applied.
int a = 1_000_000_006, b = 1_000_000_006;
Console.WriteLine($"\n(int)a * b % Mod = {unchecked(a * b) % Mod} <- wrong, a*b overflowed int first");
Console.WriteLine($"(long)a * b % Mod = {(long)a * b % Mod} <- correct");输出：
2^10 mod 1000000007 = 1024
2^1000000 mod 1000000007 = 235042059
steps for e=1000000 : 20 squarings, not a million multiplications
inverse of 3 = 333333336
3 * inverse(3) mod p = 1 <- 1, so it really is the inverse
10 / 3 mod p = 333333339
check: that * 3 mod p = 10 <- back to 10
(int)a * b % Mod = 923446813 <- wrong, a*b overflowed int first
(long)a * b % Mod = 1 <- correctPower 每轮把底数平方、指数减半，所以 2^1000000 只要平方二十次。
除法换成乘以模逆元。费马小定理说，对素数 p 有 a^(p-1) ≡ 1，所以 a^(p-2) 就是 a 的逆元。10⁹+7 是素数，于是 Inverse 只需调用一次 Power。输出验证了这一点：3 * inverse(3) ≡ 1，先除再乘能回到原来的数。
最后两行才是这个模式真正要讲的 bug。两个 int 相乘的 a * b 在 % Mod 执行之前就溢出了，结果是错的，看上去却完全合理。全程用 long，每次乘法之后都取模，不要留到最后。
适用场景： 题目写着“对 10⁹+7 取模”。计数问题、路径计数、组合数学。
模式 50 — 写出输出
这是模式 46 的镜像，而且影响更大。
Console.Out 开着 AutoFlush。每次 WriteLine 都会推到底层流，所以 200,000 行不是 200,000 次字符串操作，而是 200,000 次进出操作系统。
using System.Text;
// The cost of Console.WriteLine is not allocation — it is that AutoFlush
// pushes to the underlying stream on EVERY call. Count those pushes.
int n = 200_000;
static void Run(string name, Action<Stream> write)
{
var s = new CountingStream();
write(s);
Console.WriteLine($"{name,-26} {s.Writes,9:N0} writes to the stream {s.Bytes,10:N0} bytes");
}
Run("AutoFlush = true", s =>
{
var w = new StreamWriter(s) { AutoFlush = true }; // what Console.Out does
for (int i = 0; i < n; i++) w.WriteLine(i);
w.Flush();
});
Run("64KB buffer, no AutoFlush", s =>
{
var w = new StreamWriter(s, bufferSize: 1 << 16) { AutoFlush = false };
for (int i = 0; i < n; i++) w.WriteLine(i);
w.Flush();
});
Run("one StringBuilder", s =>
{
var sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.Append(i).Append('\n');
var w = new StreamWriter(s, bufferSize: 1 << 16) { AutoFlush = false };
w.Write(sb);
w.Flush();
});
Console.WriteLine("\nIn a real program the fix is one line at the top:");
Console.WriteLine(" Console.SetOut(new StreamWriter(Console.OpenStandardOutput(),");
Console.WriteLine(" bufferSize: 1 << 16) { AutoFlush = false });");
Console.WriteLine("and Console.Out.Flush() before returning, or the output never arrives.");
class CountingStream : Stream
{
public int Writes { get; private set; }
public long Bytes { get; private set; }
public override void Write(byte[] buffer, int offset, int count) { Writes++; Bytes += count; }
public override void Write(ReadOnlySpan<byte> buffer) { Writes++; Bytes += buffer.Length; }
public override bool CanWrite => true;
public override bool CanRead => false;
public override bool CanSeek => false;
public override long Length => Bytes;
public override long Position { get => Bytes; set => throw new NotSupportedException(); }
public override void Flush() { }
public override int Read(byte[] b, int o, int c) => throw new NotSupportedException();
public override long Seek(long o, SeekOrigin s) => throw new NotSupportedException();
public override void SetLength(long v) => throw new NotSupportedException();
}输出：
AutoFlush = true 400,000 writes to the stream 1,288,890 bytes
64KB buffer, no AutoFlush 20 writes to the stream 1,288,890 bytes
one StringBuilder 20 writes to the stream 1,288,890 bytes
In a real program the fix is one line at the top:
Console.SetOut(new StreamWriter(Console.OpenStandardOutput(),
bufferSize: 1 << 16) { AutoFlush = false });
and Console.Out.Flush() before returning, or the output never arrives.输出逐字节相同，写入次数却是四十万对二十。（是四十万而不是二十万，因为 WriteLine 把值和换行符分两次写。）
在这台机器上实测，200,000 行不带缓冲约 190 ms，经过 64KB 缓冲约 24 ms，先攒进 StringBuilder 约 15 ms。和这一篇里其他优化是同一个量级的节省，只要加一行设置。
唯一会坑到你的地方：退出前要 flush。 设了 AutoFlush = false，进程结束时还留在缓冲区里的内容就直接丢了。症状是解法在你机器上完全正常，提交却得零分。因为调试会话在退出时会 flush，评测框架却不一定。
要点
- 循环里的
Console.ReadLine通常才是正确的 C# 解法超时的原因。 不是算法。 int.Parse接受ReadOnlySpan<char>。 换个类型，再用Range做索引，几乎不费力就能去掉所有子串分配。array[a..b]会复制，span[a..b]不会。 语法一模一样，调用处看不出代价。stackalloc只用于很小的常量大小。 它和递归共用那 1MB 栈。- 用
lo + (hi - lo) / 2，累加到long，先转换再相乘。 写(long)a * b，绝不写(long)(a * b)。 - C# 不会提醒你溢出。 它只会回绕。调试时加上
checked { }，它就会在正确的那一行报出来。 - p 为素数时，
a^(p-2) mod p就是模逆元，而 10⁹+7 正是素数。用long运算，每次乘法后都取模。 - 关掉
AutoFlush，退出前记得 flush。 忘了 flush 会丢掉全部输出，看起来却像答案错了，而不是没有输出。
竞赛部分到此为止
十篇，五十个模式，从两个相向而行的整数，一直讲到决定这一切能否按时跑完的缓冲区。
把它们当成清单背下来，没多大用处。真正有用的是认出题目的形状：看到“最小化最大值”，就想到二分答案；看到“取值在 1 到 n 之间”，就想到数组本身就是哈希表；看到“恰好 K 个”，就想到把“至多”算两次再相减。形状一旦叫得出名字，代码反而是容易的部分。
后面还有六篇，风格也变了。竞赛里没人会给你链表，你拿到的是数组和时间限制。面试官会给你一个链表，然后看着你原地反转它。第 11 到 16 篇讲的就是那个房间里会出现的模式：链表、两篇二叉树、区间、回溯和位运算。
整个系列是 C# 算法模式：面试与竞赛，其中每个程序在发布前都在 .NET 10 上跑过。