题目描述
思路解析
一句话答案：LeetCode 2109 向字符串添加空格：spaces 已严格递增，双指针一趟扫——i 走原串、j 追下一个插入点，i 撞上 spaces[j] 就先补空格再放字符，时间 O(n)。
空格该插在哪，插完长什么样
给一个下标从 0 开始的字符串 s，再给一个下标数组 spaces，里面的下标从小到大排、彼此不重复。spaces 里每个下标处的字符之前，都要插进一个空格，返回插好的新串。题面例子 s 是 AlgoMoocOJ、spaces 是 [4,8]，在下标 4 的 M 前、下标 8 的 O 前各补一个空格，得到 Algo Mooc OJ。
遇一个空格就切一次串，账怎么算
照字面来：每碰到一个 spaces 下标，就在原串那里切开、插进一个空格。spaces 有 m 个下标就切 m 次，而字符串不可变，每切一次都要复制整条串，长 n 的串复制一趟就是 n 次搬运。切 m 次、每次搬 n 个字符，总代价是 O(n×m)，串一长就拖。
spaces 升序这条件，能省下什么
既然 spaces 从小到大排好，下一个要插空格的位置永远在当前位置右边、绝不回头。那就不必反复回原串切来切去，只要从左到右扫一遍 s，攥一个 j 指着 spaces 里下一个待插入的下标：扫到的字符下标要么还没够到 spaces[j]，要么正好等于它。两个各扫一条数据的指针，i 走 s、j 走 spaces，把插空格和放字符对齐。
一趟扫下来，每个字符先做哪件事
备一个可变容器（能往后追加、不用重建的列表或 StringBuilder）当答案。i 从 0 扫到串尾，每落到字符 c 先问：j 没走完 spaces、且 i 等于 spaces[j]？成立就先塞一个空格、j 前移一格；不管补没补，都无条件把 c 追加进去。i 走完，碎片拼成串就是答案。顺序不能反，先补空格再放字符。
AlgoMoocOJ、spaces=[4,8] 逐格过每步
s 是 AlgoMoocOJ，下标 0 到 9，spaces 是 [4,8]，j 从 0 起。i 从 0 走到 3 都不等于 spaces[0]，A、l、g、o 挨个进容器，攒成 Algo。
i 到 4 命中 spaces[0]：塞空格、j 到 1、放 M，成 Algo M。i 走 5、6、7 都不命中，o、o、c 追加成 Algo Mooc。i 到 8 命中 spaces[1]：塞空格、j 到 2、放 O，得 Algo Mooc O。i 到 9 时 spaces 已用尽，守卫不成立，跳过补空格直接放 J，成 Algo Mooc OJ。
取 spaces[j] 前不看 j，串一扫完就崩
取 spaces[j] 之前得先确认 j 没走出 spaces：用完后 j 等于它的长度，再读 spaces[j] 就摸到数组外面，越界会报错或读到脏值，守卫必须挡在取值前。空格落点也松不得，题目要在触发字符之前插，塞到后面整条串就错位。攒答案别用加号在循环里硬拼不可变字符串，每加一次都重建整串、代价滚回 O(n×m)；切片重建整串是同一个坑，一遍扫描追加才线性。
扫描只碰每个字符一次，i 单遍走、j 只增不减，前移总次数不超过 spaces 长度，时间 O(n)；答案串比原串多 m 个空格，长度 n 加 m 量级，空间 O(n)，辅助只用两个下标是 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:i 扫字符,j 追下一个要插空格的位置,i 撞上 spaces[j] 就先补一个空格再把字符追进去。整趟只扫一遍,又快又稳。下面从头开始拼。
开工布局 · i 从 0 开始,ans 还空着：布局摆好。上面这条是原串 AlgoMoocOJ,每个格子下面是它的下标。右边面板是 spaces 数组,现在 j 指着第 0 行、值是 4,意思是下一个要在它前面补空格的位置是下标 4。下面这行 ans 是我们要拼的答案,现在还空着。指针 i 从 0 出发。
看 i=0 · 该不该在它前面补空格：指针 i 走到 0,和 spaces[0] 也就是 4 比一比,0 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[0]=A 进 ans：不管刚才插没插空格,当前字符 A 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「A」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=1 · 该不该在它前面补空格：指针 i 走到 1,和 spaces[0] 也就是 4 比一比,1 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[1]=l 进 ans：不管刚才插没插空格,当前字符 l 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Al」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=2 · 该不该在它前面补空格：指针 i 走到 2,和 spaces[0] 也就是 4 比一比,2 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[2]=g 进 ans：不管刚才插没插空格,当前字符 g 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Alg」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=3 · 该不该在它前面补空格：指针 i 走到 3,和 spaces[0] 也就是 4 比一比,3 不等于 4,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[3]=o 进 ans：不管刚才插没插空格,当前字符 o 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=4 · 该不该在它前面补空格：指针 i 走到 4,拿它和 spaces[0] 也就是 4 比一比,正好相等,命中了!这说明当前字符 M 之前该补一个空格。先别急着放字符,下一步先把空格补上。
命中!在 s[4]=M 之前补一个空格：命中了就先补空格。往 ans 末尾放一个空格,你看答案串在字符 M 之前多了一个空格。补完把 j 往后挪一格,从 0 变成 1,面板高亮跟着移到下一个待插入的位置(下标 8)。空格补好了,接着才轮到字符。
追加 s[4]=M 进 ans：不管刚才插没插空格,当前字符 M 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo M」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=5 · 该不该在它前面补空格：指针 i 走到 5,和 spaces[1] 也就是 8 比一比,5 不等于 8,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[5]=o 进 ans：不管刚才插没插空格,当前字符 o 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mo」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=6 · 该不该在它前面补空格：指针 i 走到 6,和 spaces[1] 也就是 8 比一比,6 不等于 8,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[6]=o 进 ans：不管刚才插没插空格,当前字符 o 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Moo」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=7 · 该不该在它前面补空格：指针 i 走到 7,和 spaces[1] 也就是 8 比一比,7 不等于 8,说明这个位置前面不用加空格。那就跳过补空格这步,直接去追加字符。
追加 s[7]=c 进 ans：不管刚才插没插空格,当前字符 c 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mooc」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=8 · 该不该在它前面补空格：指针 i 走到 8,拿它和 spaces[1] 也就是 8 比一比,正好相等,命中了!这说明当前字符 O 之前该补一个空格。先别急着放字符,下一步先把空格补上。
命中!在 s[8]=O 之前补一个空格：命中了就先补空格。往 ans 末尾放一个空格,你看答案串在字符 O 之前多了一个空格。补完把 j 往后挪一格,从 1 变成 2,这下 spaces 里两个下标都用过了、j 已用完,后面不再有待插入的位置,面板高亮也随之撤掉。空格补好了,接着才轮到字符。
追加 s[8]=O 进 ans：不管刚才插没插空格,当前字符 O 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mooc O」。这一格处理完,指针 i 往右挪一步,去看下一个字符。
看 i=9 · 该不该在它前面补空格：指针 i 走到 9,看右边面板,j 已经等于 2,spaces 两个下标都用完了。既然没有待插入的位置了,就跳过检查,直接去追加这个字符。这一步演示的就是 j 用尽后的收尾。
追加 s[9]=J 进 ans：不管刚才插没插空格,当前字符 J 都要放进答案。把它追加到 ans 末尾,现在答案变成了 「Algo Mooc OJ」。这一格是原串最后一个字符,处理完 i 就到达串尾之后的位置,下一步进入扫描结束、开始收束。
扫描结束 · 答案拼好：整条串扫完了。回头看,我们只在两处补了空格:下标 4 的 M 前面、下标 8 的 O 前面,这两个触发字符标成了绿色。最后拼出来的答案就是 「Algo Mooc OJ」,和一开始说的 Algo Mooc OJ 分毫不差。全程只扫了一遍,双指针配合得干净利落。
边界想清:空格可以补在最前面、也可以补在最后一个字符之前;每个 spaces 值都落在有效下标内,严格递增不会重复。
面试重点:双指针单遍、命中先补空格再追加、用可变容器攒串避免 O(n 方)、时间空间都是 O(n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def addSpaces(self, s: str, spaces: List[int]) -> str: ans = [] j = 0 for i, c in enumerate(s): if j < len(spaces) and i == spaces[j]: ans.append(' ') j += 1 ans.append(c) return ''.join(ans)复杂度
- 时间：O(n)，n 是原串长度。i 从头扫到尾只走一遍,每个位置最多补一个空格加追加一个字符,都是常数操作;j 一路只增不减,总共前移的次数等于 spaces 的长度,不超过 n。合起来随 n 线性增长
- 空间：O(n)，按峰值算,主要花在攒出来的答案串上:它比原串多了 spaces 长度个空格,长度是 n 加 m 量级,也就是 O(n)。除答案外只用了 i、j 两个下标,额外辅助空间是 O(1)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问为什么要用可变容器攒答案,直接字符串相加不行吗?
追问时间和空间复杂度各是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最少交换次数来组合所有的 1 II
LeetCode 2134 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题