把一段字符串原地压短听起来像是个再简单不过的操作但真到了面试现场或者刷题平台不少人会在“原地”“计数转字符”“最后一段收尾”这些地方卡住。我最早接触这道题是在准备算法工程师面试的时候当时觉得 LeetCode 上的“压缩字符串”不过是个 easy 级别的模拟题结果手写代码时连续踩了两个坑后来才意识到这道题考察的远不止“会不会写循环”而是对双指针、原地修改、边界处理这套基本功的熟练度。这道题适合正在刷 LeetCode 基础题的人、准备面试的候选人以及想巩固字符串双指针套路的朋友。它不需要什么高深的数据结构但能把“看似暴力、实则优雅”的思维过程完整呈现一遍。下面我按照自己从读题到实现、再到调试的经验把这个题目彻底拆开聊清楚。1. 题目到底在考什么读懂“压缩字符串”的潜台词先还原一下题目本身。给定一个字符数组chars要求原地压缩把连续出现的相同字符压缩成“字符 出现次数”的形式比如[a,a,b,b,b]压缩后应该变成[a,2,b,3]。压缩后的长度必须小于等于原长度最终返回新数组的长度。如果某个字符只出现一次就保留这个字符本身不额外拼接数字“1”。题目还额外强调了一句不要使用额外的数组空间必须原地修改输入数组。1.1 这道题源自哪里常见变体长什么样这道题最常见的原型是 LeetCode 443 题 “String Compression”在中文社区里经常被称为“压缩字符串”。面试中它还可能以变体出现比如“只统计连续相同字符并输出压缩后的字符串”“给定一个字符串流实时输出当前压缩长度”“解压缩字符串”等。但不管外衣怎么换内核对准的都是同一套能力识别连续段、记录段长、原地回写。为什么面试官喜欢出这道题因为它足够小十分钟内能写完又足够巧能区分出“背过模板”和“真正理解双指针”的候选人。它不考记忆库考的是临场拆解问题的能力。1.2 三个隐藏考点原地、分组、计数转文本第一是“原地”。这意味着你不能新开一个vectorchar来存放结果再整体拷贝回去。空间复杂度被锁死在 O(1)用辅助数组的思路直接出局。第二是“分组”。压缩的对象不是全局去重而是“连续段”。比如[a,b,a]中两个a不相邻就不能合并成[a,2,b]。第三是“计数转文本”。当同一字符连续出现超过 9 次时次数变成两位数甚至三位数需要拆成多个字符写回原数组。这三件事单独拆开都不难但组合在一起时代码的指针关系就会变得微妙起来。这恰恰是这道题真正的价值所在。1.3 边界条件与隐藏要求越早列清越省事边界条件主要有三个空数组、只有一个字符、单个字符连续出现很多次。空数组直接返回 0[a]返回 1 且什么都不用改[a,a,...,a]12 个a压缩后应该是[a,1,2]返回 3。这里最容易出错的是最后一种数字 12 需要拆成两个字符1和2写入顺序不能反。还有一条隐藏要求容易被忽略题目说压缩后的长度必须始终小于或等于原数组长度。对于纯小写字母、连续段较多的输入这条基本天然满足但如果你把逻辑写成“每段都写字符次数”对单字符段写了1长度可能不会变长但不符合题目要求。所以必须记住成对出现的次数大于 1 时才写数字等于 1 时跳过。2. 从暴力到双指针为什么最优解是“读写分离”看到这道题第一反应可能是遍历数组统计每一段然后生成一个新字符串最后把新字符串搬回原数组。这个思路完全正确但它违背了“原地”约束。那是不是原地做不到呢不是的关键要转换视角。2.1 暴力解法的致命伤空间换时间的惯性思维暴力解法的实现大概是这样先遍历一遍把每个连续段拆成字符 次数放入一个临时数组然后整体覆盖原数组。这种写法的时间复杂度是 O(n)空间复杂度也是 O(n)在 LeetCode 上其实能通过因为字符数组本身的长度有限。但面试官问你“能不能优化空间”时如果答不上来这题在你这里的评价就会大打折扣。我见过不少人卡在“把结果写回原数组会覆盖还没读到的字符”这个担忧上。这个担忧确实需要认真分析但它不是无解的而是要通过指针设计来规避。2.2 双指针的灵感来源读指针负责看写指针负责写双指针的思路说起来很简单一个指针read负责向前扫描另一个指针write负责在数组前面依次写入压缩结果。读指针走过的区域写指针通常不会超过它所以理论上不会覆盖尚未读到的内容。这个“写指针永远追不上读指针、或者刚好等于读指针”的结论是整道题正确性的基石。为什么写指针不会超过读指针因为压缩后的长度永远不会超过原长度。每一段压缩后写成字符 数字当连续字符数为 1 时写 1 个字符等于原长度当连续字符数超过 1 时写 1 个字符加若干数字字符位数一定小于原来的段长。所以整体上写指针的累计前进速度慢于读指针。这个性质保证了原地操作的安全性。2.3 双指针代码骨架三段式结构一般双指针实现在结构上可以分成三段。第一段是初始化read 0, write 0并定义一个变量start用来标记当前连续段的起点。第二段是主循环read从 0 遍历到末尾每当chars[read] ! chars[start]时说明一个连续段结束了立即处理从start到read - 1的这一段处理完把start更新为read。第三段是收尾循环结束后start到数组末尾可能还有最后一段不要忘了处理。这个骨架几乎是所有“按连续段处理”题目的通用解法比如字符串中的单词拆分、按段落反转等都可以类比。3. 代码实现与逐步走读一份可直接复用的 C 参考下面给出我用 C 写的版本。选 C 是因为刷题和面试中 C 出现的频率很高而且vectorchar的接口很直观后面我再补充 Python 版本的对比和注意事项。#include vector #include string using namespace std; class Solution { public: int compress(vectorchar chars) { int n chars.size(); if (n 1) return n; int write 0; // 写指针 int start 0; // 当前连续段的起始下标 for (int read 0; read n; read) { // 当遇到新字符或者遍历到最后一个字符时需要处理一段 if (read n - 1 || chars[read] ! chars[read 1]) { // 处理从 start 到 read 的连续段 chars[write] chars[start]; int count read - start 1; if (count 1) { string countStr to_string(count); for (char c : countStr) { chars[write] c; } } start read 1; } } return write; } };3.1 主循环的写法边界判断放在循环里还是循环外我上面的版本把“最后一段”的处理通过read n - 1 ||这个条件并入了主循环这样循环结束后就不需要额外收尾。还有另一种写法是循环结束后单独处理start到n - 1这一段。两种写法都对但我觉得第一种更统一不容易漏掉边界。不过它有一个小问题每次循环都要判断read n - 1稍有一点额外开销但对于算法题来说完全无所谓。如果你更习惯第二种写法逻辑是这样的主循环里只在chars[read] ! chars[start]时处理一段循环结束后再处理start到最后这一段。这两种写法我在面试中都写过个人推荐第一种因为它把“最后一段”纳入了同一个逻辑分支代码短一些面试时也更好解释。3.2 数字写回的正确姿势先算位数再按高位到低位逐个写当count大于 1 时需要把整数转成字符串。直接用to_string(count)是最省事的方式它会自动把 12 拆成12并依次写入1、2。如果面试官说“不能用标准库”那就需要手动转换。手动转换的思路是先用一个临时字符串或字符数组保存每一位数字然后把它们按正确的顺序写入chars。很多人会先对count做% 10拿到最低位然后写入但这样写出来的数字是反的比如 123 会写成3,2,1。正确的做法是先把每一位存到临时数组里最后再倒序写入或者采用“从高位到低位”的方式先计算count的位数再依次取出最高位。一个我常用的技巧是先把各位存进一个char tmp[16]用一个索引idx从 0 开始记录然后倒序写入。说白了就是手动实现一个itoa。这样写虽然代码长一点但逻辑清晰不容易出错。3.3 为什么write指针不会覆盖未读字符这里有一个值得展开的点。假设输入是[a,a,a,b,b,c]读指针read走到下标 2 时发现chars[3]是b于是处理start 0到read 2这一段。此时write在位置 0写入chars[0] a然后写入3到位置 1。当read继续走到下标 3、4 时它读的是b,b而位置 1 已经被改成了3但位置 1 早就被读过了所以不影响后续判断。关键点在于写指针写入的位置一定在已经处理完的区域里。因为写指针的推进速度慢于读指针所以它永远不会追到读指针前方。掌握了这条性质就不用担心原地覆盖会导致数据丢失。3.4 复杂度分析与正确性说明整个算法只扫了一遍数组每个字符最多被读一次、被写一次时间复杂度是 O(n)。空间方面除了一两个指针变量和临时字符串没有使用额外数组空间复杂度是 O(1)严格来说to_string会分配一个临时字符串但它的长度是数字的位数与输入规模无关的常数级可以忽略。正确性可以从不变量的角度来证明在第k次处理完一段后chars的前write个位置已经存放了前k段的压缩结果read始终位于尚未处理的区域。这样循环不变量就保证了最终结果是正确的。4. 面试和刷题中常见的错误与排查实录这部分我结合自己实际调试时的经验把最容易踩的坑整理成清单。有些坑是逻辑问题有些是对题目理解不到位还有些是 C 细节都有必要单独拿出来说。4.1 错误一循环结束后忘了处理最后一段这是我最早犯的错误。如果主循环只在检测到“当前字符和下一个字符不同”时处理段那么数组结尾处的那一段永远不会被触发因为后面没有下一个字符了。如果不额外处理[a,a,b,b]会只压出[a,2]后面b段直接丢掉了。解决办法就是 3.1 里说的两种方案要么在循环里用read n - 1 ||主动触发收尾要么循环结束后单独处理。我建议在代码里刻意写一条注释“handle the last segment”提醒自己也提醒面试官。4.2 错误二数字位的写入顺序搞反了如果不用to_string手动把整数 123 拆成字符时容易写出3,2,1。直观原因是我们习惯用while (count) { tmp[i] count % 10 0; count / 10; }这样得到的 tmp 是反的。解决办法是倒序写回或者先算位数再正向取值。我自己常用的正向写法是先求位数len to_string(count).size()然后从最高位开始char c 0 (count / pow(10, len - 1)) % 10但这样涉及到浮点运算没必要。更推荐的做法是存到临时数组再倒序逻辑最稳妥。4.3 错误三单字符段错误地写入了数字“1”题目明确要求连续出现 1 次的字符只保留字符本身不需要加1。如果每个段都无脑写字符 count那么[a,b,c]会被压成[a,1,b,1,c,1]返回长度 6而正确答案是返回 3。这个错误在测试用例是长串重复字符时不容易暴露但一旦输入变成全异字符就会立刻现形。我见过一些题解在if (count 1)里漏掉了这个判断结果提交后挂在某个全异字符的用例上。所以写代码时一定要把count 1的情况单独想清楚。4.4 边界输入与压力测试一组合格的自测用例刷题时我习惯自己构造几组用例来验证不直接交到评测系统里试错。针对这道题我常用的自测用例有这些输入期望输出说明[]0空数组[a]1单字符[a,b,c]3无重复字符全不压缩[a,a,b,b,c,c,c]6结果为[a,2,b,2,c,3]标准示例[a,b,b,b,b,b,b,b,b,b,b,b,b]4结果为[a,b,1,2]注意a是单字符不加数字b出现 12 次要写成1,2[a,a,a,a,a,a,a,a,a,a]3结果为[a,1,0]10 次要写成两位我每次改完代码都会把这几组用例手动跑一遍再上平台提交。省下来的时间比多提交几次多得多。4.5 从压缩字符串到字符串处理套路这套思路还能用在哪双指针“读写分离”的思路不止能解决这一道题。类似的还有原地删除元素、移动零、去除重复字母等。它们共享同一个套路用读指针扫描源数据用写指针维护结果区两者交错推进。沿着这个套路继续延伸你会发现很多“原地操作数组”的题其实都是同一个模型。比如 LeetCode 27 移除元素要求原地删除值等于目标值的元素比如 LeetCode 26 删除有序数组中的重复项再比如移动零。这些题一旦你掌握了“读指针负责发现、写指针负责保留”的思路基本都能秒解。压缩字符串这道题在面试中还有一个常见追问“如果连续段特别长比如几万个相同字符你的算法还能用吗”答案当然是能因为复杂度只和数组长度有关和单段长度无关。但如果面试官让你进一步优化写回的字符数量那就要考虑用更大的基数比如用 base-64 来表示计数器这属于额外拓展一般不会在核心题里要求。5. 写在最后的一点个人体会这道题我前前后后写过不下五种版本暴力临时数组版、循环内收尾版、循环外收尾版、手动数字转换版还有 Python 版本。每种版本都让我对“原地修改”和“细节边界”有了更深的理解。我印象最深的一次是在面试中我把主循环条件写成read n然后在循环体里用chars[read] ! chars[start]处理段结果最后一段漏掉了。面试官提示我“数组末尾怎么办”我现场加了一段收尾逻辑才救回来。那次以后我再也没忘过。如果你现在正在准备面试我建议你拿到这道题后先不要马上写代码而是把三种边界条件空数组、单字符、纯重复字符在纸上推演一遍再动手写。写完以后用上面那几张表里的用例自查一遍。整个过程花不了二十分钟但带来的收益是实打实的。另外一个小技巧面试时如果要求现场写代码可以先把“读指针、写指针、段起点”这三个变量的作用用一句话说给面试官听再开始写。这样即使代码中间有小 bug面试官也知道你的思路是对的他们会更宽容地看待后续的修正过程。这一点在我自己和后来帮别人模拟面试时都反复验证过非常管用。