字符串压缩如何用双指针原地写回？（LeetCode 443）

简化版

字符串压缩把连续相同字符写成字符加次数，例如 aaabb 压成 a3b2。用读指针扫描每一段连续字符，用写指针把字符和计数字符逐个写回原数组。单个字符不写次数。

详细版

int compress(char[] chars) {
    int write = 0, read = 0;
    while (read < chars.length) {
        char c = chars[read];
        int start = read;
        while (read < chars.length && chars[read] == c) read++;
        int count = read - start;
        chars[write++] = c;
        if (count > 1) {
            for (char d : String.valueOf(count).toCharArray()) {
                chars[write++] = d;
            }
        }
    }
    return write;
}

读指针永远在前面扫描原始段，写指针只写压缩结果。题目保证压缩后长度不超过原数组可容纳范围。

完整版教学

一、题目考的是原地写回

不是返回一个新字符串，而是修改输入数组前 k 个位置，并返回 k。这意味着要同时管理读取位置和写入位置。

input:  a a a b b c
output: a 3 b 2 c
return: 5

数组后面的旧内容不用清空，评测只看返回长度内的部分。

二、为什么需要分段扫描

连续相同字符构成一段。每段只输出两类信息：

段内容	输出
`a`	`a`
`aaa`	`a3`
`bbbbbbbbbbbb`	`b12`

所以算法天然是“找到一段 -> 写字符 -> 如果数量大于 1，再写数量”。

三、读指针和写指针的职责

read 负责向右找当前段结尾，write 负责写压缩结果。

int start = read;
while (read < n && chars[read] == c) read++;
int count = read - start;

这一段结束后，read 已经停在下一段开头，count 是当前字符出现次数。

四、为什么原地写不会覆盖未读数据

压缩结果长度不会超过已读部分长度。对于每一段：

长度 1 -> 输出 1
长度 k>=2 -> 输出 1 + digits(k) <= k

例如 k=12 输出 3 个字符 a12，仍小于等于 12。这保证写指针不会跑到读指针前面覆盖未处理字符。

易错点：这条性质是原地算法安全的关键。不是因为“看起来 write 比 read 慢”，而是每段压缩长度不超过原段长度。

五、计数要逐位写入

次数可能是两位或更多，比如 12 要写成 '1'、'2' 两个字符，不能写成一个整数。

for (char d : String.valueOf(count).toCharArray()) {
    chars[write++] = d;
}

如果只写 count + '0'，当 count 超过 9 时就错。

六、边界例子

["a"] -> ["a"], return 1
["a","a"] -> ["a","2"], return 2
["a" repeated 12] -> ["a","1","2"], return 3
["a","b","c"] -> ["a","b","c"], return 3

单字符段不写 1，这是很多人第一次写会错的规则。

七、常见误区与追问

误区：为单个字符写入次数 1。 题目要求单个字符只写字符本身。
误区：把两位数次数当成一个字符写。 12 必须拆成 '1' 和 '2'。
误区：担心原地写一定覆盖未读内容。 每段压缩后长度不超过原段长度，所以安全。
追问：为什么空间是 O(1)？ 除了几个变量和计数字符临时转换，不创建与输入同规模的新数组。
追问：如果压缩后更长怎么办？ 这道题的规则下不会更长；其他压缩规则要重新证明。
追问：返回值代表什么？ 返回压缩后有效前缀长度，数组后续旧值无意义。

八、加强记忆

字符串压缩的节奏是“读一段，写字符，必要时写数字”。read 找段，write 写答案；单个字符不写 1，多位数字拆开写。原地安全靠每段输出长度不超过输入段长度，这是面试里最值得主动讲的一句。

简化版

详细版