CS-Notes 剑指 Offer 题解：从后向前双指针原地改写字符串（5. 替换空格）

本篇围绕 CS-Notes 仓库 [剑指 Offer 题解系列](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/剑指 Offer 题解 - 目录.md?utm_source=gitcode_repo_files) 中的第 5 题“替换空格”展开：将一个字符串中的空格替换为 %20，核心解法是用 P1、P2 两个从后向前的指针在 StringBuffer 尾部就地填充，实现 O(n) 时间、O(1) 额外空间的原地改写。读完后你能掌握“先统计后改写”的双指针模板、为什么必须从后向前遍历，以及该方案在时间/空间复杂度上优于常规拼接写法的完整原因。

题目描述

将一个字符串中的空格替换成 "%20"。

Input:
"A B"

Output:
"A%20B"

该题出自《剑指 Offer》的“数组与矩阵”分类，是考察字符串（字符序列）原地改写的经典入门题。它对应的题解全文见 [5. 替换空格](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/5. 替换空格.md?utm_source=gitcode_repo_files)，在 [题解目录](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/剑指 Offer 题解 - 目录.md?utm_source=gitcode_repo_files) 中归入“数组与矩阵”小节。

解题核心：统计空格 + 从后向前双指针填充

题解给出的思路分三步，下面逐步展开并结合实现细节说明。

第一步：统计空格数量，在尾部预填充

一个空格要替换成 3 个字符（%20），长度净增 2。因此先从前向后扫一遍原串，每遇到一个空格就在 StringBuffer 尾部 append 两个任意字符（题解代码里用两个空格占位），使总长度恰好等于替换后的长度：

int P1 = str.length() - 1;
for (int i = 0; i <= P1; i++)
    if (str.charAt(i) == ' ')
        str.append("  ");

这一步结束后：

• P1 仍指向原字符串的末尾；
• P2 = str.length() - 1 指向扩展后的末尾；
• 两者之差 P2 - P1 = 2 × 空格总数，这个差值正是后续改写过程中始终守恒的不变量。

为什么用 StringBuffer 而不用普通 String？String 不可变，任何改写都会产生新对象，无法原地修改；而 StringBuffer 支持 append 与 setCharAt 下标改写，配合“尾部追加”恰好可以避开对已有内容的挪动——追加发生在原串之后的空白区，不会破坏 P1 还要读取的原始字符。

第二步：P1 与 P2 从后向前遍历

int P2 = str.length() - 1;
while (P1 >= 0 && P2 > P1) {
    char c = str.charAt(P1--);
    if (c == ' ') {
        str.setCharAt(P2--, '0');
        str.setCharAt(P2--, '2');
        str.setCharAt(P2--, '%');
    } else {
        str.setCharAt(P2--, c);
    }
}

遍历规则：

• P1 每步向左移动一位，读取原始字符；
• 若读到空格，P2 所在位置依次写入 0、2、% 三个字符（注意是逆序写入：最高位先放 '0'、再放 '2'、最后放 '%'，从左到右看正好拼成 %20），P2 前进 3 位；
• 否则把 P1 处的字符原样复制到 P2，两者各前进 1 位。

为什么必须从后向前？ 这是本解法最关键的点。改写时写入的位置（P2）始终在读取位置（P1）的右侧：每处理一个非空格，P1、P2 同步左移，差值不变；每处理一个空格，P2 比 P1 多走 2 位，差值减少 2——恰好抵消该空格在第一步预填充时贡献的 2。因此写入永远不会落在 P1 尚未读取的字符上。反之，若从前向后改写，第二个空格替换产生的 3 个字符会立刻覆盖其右侧还没被 P1 读到的原始字符，数据就丢失了。

第三步：终止条件

题解原文给出的退出条件是“当 P2 遇到 P1 时（P2 <= P1），或者遍历结束（P1 < 0），退出”，对应代码中的 while (P1 >= 0 && P2 > P1)。结合上面的不变量可以推断：只要字符串里至少有一个空格，P2 就始终严格大于 P1，此时真正起决定作用的是 P1 >= 0；若字符串没有空格，P2 与 P1 初始就相等，循环第一轮后两者同步左移保持相等，P2 > P1 不成立直接退出——等价于把原串逐字符复制到自身，结果不变，也安全覆盖了“无空格”这一边界。

完整实现

以下为题解仓库中的完整 Java 实现（[源码见原文件](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/5. 替换空格.md?utm_source=gitcode_repo_files)）：

public String replaceSpace(StringBuffer str) {
    int P1 = str.length() - 1;
    for (int i = 0; i <= P1; i++)
        if (str.charAt(i) == ' ')
            str.append("  ");

    int P2 = str.length() - 1;
    while (P1 >= 0 && P2 > P1) {
        char c = str.charAt(P1--);
        if (c == ' ') {
            str.setCharAt(P2--, '0');
            str.setCharAt(P2--, '2');
            str.setCharAt(P2--, '%');
        } else {
            str.setCharAt(P2--, c);
        }
    }
    return str.toString();
}

几个可以结合代码验证的边界情况：

输入	过程	输出
"A B"	1 个空格，尾部补 2 位；P2 依次写 B、0、2、%、A	"A%20B"
""（空串）	P1 = -1，两个循环都不执行	""
"AB"（无空格）	不追加，P2 == P1，循环直接退出	"AB"
" "（2 个空格）	尾部补 4 位，P2 依次写两组 02%	"%20%20"

复杂度分析

从上述实现可以直接得出：

• 时间复杂度 O(n)：第一步 for 循环扫描原串一次；第二步每个原始字符恰好被 P1 读取一次，setCharAt 是 O(1) 的下标写入。全程没有对已填充区间的整体搬移。
• 额外空间 O(1)：只在传入的 StringBuffer 上原地改写（toString() 返回的副本不计入），辅助变量仅有 P1、P2、c 等常数个。

作为对比，最直接的“新建字符串拼接”写法是 O(n) 空间：

public String replaceSpace(StringBuffer str) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < str.length(); i++)
        sb.append(str.charAt(i) == ' ' ? "%20" : str.charAt(i));
    return sb.toString();
}

两种写法时间上都是 O(n)，但双指针方案在“容器容量允许、必须原地修改”的场景下省去了一个与结果等长的缓冲区，这正是剑指 Offer 系列偏爱它的理由。

在仓库中的定位与延伸

• 本题在 [剑指 Offer 题解目录](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/剑指 Offer 题解 - 目录.md?utm_source=gitcode_repo_files) 中属于“数组与矩阵”分类，与“3. 数组中重复的数字”“4. 二维数组中的查找”“29. 顺时针打印矩阵”等题并列，是字符数组原地操作的第一个练习。
• 目录中的“双指针”分类下还有 [57.1 和为 S 的两个数字](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/57.1 和为 S 的两个数字.md?utm_source=gitcode_repo_files)、[57.2 和为 S 的连续正数序列](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/57.2 和为 S 的连续正数序列.md?utm_source=gitcode_repo_files)、[58.1 翻转单词顺序列](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/58.1 翻转单词顺序列.md?utm_source=gitcode_repo_files)、[58.2 左旋转字符串](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/58.2 左旋转字符串.md?utm_source=gitcode_repo_files)。其中 [58.2 左旋转字符串](https://gitcode.com/GitHub_Trending/cs/CS-Notes/blob/b70121d377cb6005eb65f12b098cd5decd905669/notes/58.2 左旋转字符串.md?utm_source=gitcode_repo_files) 与本题同属“对字符序列做原地改写”的套路——它用三次区间翻转（先翻转 abc 与 XYZdef，再整体翻转）在 O(1) 空间内完成子串交换，可与本题的“尾部填充 + 逆向填充”互相印证：原地改写的通用手段就是让写指针永远不追上读指针，或者只在不重叠的区间内操作。

掌握本题模板（统计增补量 → 尾部预填充 → 双指针从后向前改写）后，面对一切“替换导致变长且要求原地完成”的字符串题都可以直接套用。