今天进入代码随想录算法训练营的第8天字符串专题正式开篇。第一道题就是 LeetCode 344“反转字符串”说实话刚看到题目的时候我觉得这题也太简单了直接反向遍历拷贝一个新数组不就完事了吗但真正动手做才发现题目里的限制条件直接把这条路堵死了——要求原地修改输入数组空间复杂度只能是 O(1)。这就逼着你必须换思路也是从这道题开始我才真正体会到“算法题不是让你做出来而是让你用最合适的方式做出来”这句话的含义。这道题在训练营里被归为“字符串基础”类目但它考察的核心其实是双指针思想在数组操作中的应用。字符串在不少语言里本质就是字符数组所以反转字符串的操作方式和反转数组完全一致。学会这道题后面处理反转字符串 II、反转字符串中的单词、旋转字符串等问题时会少走很多弯路。1. 题目解读与思路演进为什么越简单的题越不能大意1.1 题目真正的限制条件与解题方向LeetCode 344 的原题描述非常简洁编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出不要给另外的数组分配额外空间你必须原地修改输入数组、使用 O(1) 的额外空间完成这一操作。很多人初次接触时会忽略最后这句话的份量。不要分配额外空间意味着你不能新建一个数组然后倒着填回去这是最直接但完全不符合要求的做法。你必须在这个数组本身内部完成元素的重新排列这就把解题方向强制引导到了“交换”思路上。既然要做交换那么最朴素的直觉就是把第一个字符和最后一个字符换位置把第二个字符和倒数第二个字符换位置……一直换到中间位置为止。这个过程天然带有“从两边向中间逼近”的结构特征也就是双指针法最典型的应用场景之一。提示这道题其实在考你两个能力。第一是能不能看穿“字符串在底层就是字符数组”这一层第二是能不能把“原地修改”这个约束转化为“对称位置交换”的具体操作方案。1.2 暴力解法为什么不行从工程视角看空间代价先说说那个“反向遍历赋值”的暴力方案。思路很简单遍历原数组从后往前取元素依次放到一个新数组里最后再把新数组的值复制回原数组。从结果上看原数组确实被反转了但从空间角度看它额外申请了一个长度等于原数组大小的空间。在刷题阶段很多人对空间开销不敏感觉得多一个数组又怎么了。但在实际工程里这种操作方式代价很高。假如你在处理一个非常大的字符串极端情况下可能是几十 MB 甚至上百 MB 的文本数据再复制一份出来内存占用直接翻倍。而且在某些嵌入式或资源受限的环境里额外的空间分配会导致内存碎片化甚至分配失败。所以 LeetCode 把“空间复杂度 O(1)”直接写在题目要求里不是故意卡你而是引导你训练一种思维习惯能用交换解决的问题就不要用复制来解决。这也是算法训练里“最优解意识”的起点遇到问题先问一句当前这个操作必须额外占空间吗能不能原地完成2. 双指针解法从原理到代码的完整推演2.1 双指针的思路拆解left 与 right 的相遇逻辑双指针的写法非常直观。设置两个指针left 指向数组开头right 指向数组末尾。每次迭代做两件事交换s[left]和s[right]指向的元素然后 left 向右移动一位、right 向左移动一位。重复这个过程直到两个指针相遇或者 left 超过 right。这里有一个值得细想的点为什么判断条件是left right而不是left ! right因为当数组长度为奇数时两个指针最终会在正中间的元素上相遇。此时 left 等于 right这个中间元素不需要和自己交换循环继续下去没有意义所以用更安全。当数组长度为偶数时两个指针永远不会相等但 left 会在某一步越过 right此时交换已经全部完成。从数学角度看这个过程的本质是利用了数组索引的对称性。对于一个长度为 n 的数组索引 i 的对称位置是n - 1 - i。双指针写法本质上就是在反复应用这个公式只是用指针移动代替了每次的索引计算代码更简洁逻辑也更直观。2.2 代码实现Python 与 C 双版本逐行解读先看训练营里最常使用的 Python 版本class Solution: def reverseString(self, s: List[str]) - None: left, right 0, len(s) - 1 while left right: s[left], s[right] s[right], s[left] left 1 right - 1这段代码非常短但每一行都有意义。left, right 0, len(s) - 1完成初始化把两个指针放到数组的两端。while left right是循环继续的条件保证交换操作只会在还有未处理元素时执行。s[left], s[right] s[right], s[left]是 Python 的元组解包交换写法一句搞定交换。最后left 1; right - 1完成指针向中间移动。再来看 C 版本因为在一些面试场景中 C 更常被要求手写class Solution { public: void reverseString(vectorchar s) { int left 0; int right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } } };C 里直接用swap函数底层实现是三次赋值操作这里不多展开。两个版本的逻辑完全相同区别只在于语言层面的交换写法。注意right的初始值是s.size() - 1不是s.size()。这是新手最容易犯的越界错误。数组索引从 0 开始最后一个元素的索引是长度减 1如果直接用s.size()去访问会直接导致越界错误。2.3 交换操作的三种写法与取舍分析交换两个元素是这道题的核心操作写法的选择会影响代码的可读性和适用场景。第一种是临时变量法这应该是所有人最早接触的交换方式char temp s[left]; s[left] s[right]; s[right] temp;优点是逻辑直白任何语言都能写缺点是引入了一个额外的临时变量。但这个临时变量是单个变量不随数组长度增长空间复杂度依然是 O(1)完全满足题目要求。第二种是 Python 的元组解包交换也就是上面代码里那种写法。它实际上是在底层创建了临时元组但语法层面看起来非常简洁。在 Python 生态里这种写法被广泛接受也是 LeetCode 题解区最常见的写法。第三种是异或交换利用异或运算的性质完成交换而不需要临时变量s[left] ^ s[right]; s[right] ^ s[left]; s[left] ^ s[right];这种写法看起来很高端但在实际开发中并不推荐。首先可读性差不熟悉位运算的人看到这行代码会一脸懵。其次异或交换在极端情况下可能出问题比如两个指针指向同一个位置时连续异或会把元素变成 0。我个人在实际刷题中的体会是不要为了炫技去用异或交换临时变量法或者 Python 的解包写法已经足够好。算法题的核心是思路清晰不是操作花哨。3. 边界条件与调试实录那些让你怀疑人生的细节3.1 奇偶长度对循环条件的影响验证数组长度的奇偶性会影响双指针的相遇方式这个问题我在初学时一度搞不清后来用实际推演才完全通透。当数组长度是奇数比如[a, b, c]初始 left 指向索引 0right 指向索引 2。第一次交换后变成[c, b, a]left 变为 1right 变为 1。此时 left 等于 right循环条件left right为假循环停止。中间的元素 “b” 不需要动因为它本来就在最终的对称位置上。当数组长度是偶数比如[a, b, c, d]初始 left 指向 0right 指向 3。第一次交换后 left 变为 1right 变为 2此时 left 仍然小于 right继续交换。交换完成后 left 变为 2right 变为 1此时 left 大于 right循环停止。两个案例对照下来可以发现用作为循环条件无论奇偶都能正确处理。如果用!作为条件在偶数长度时两个指针会交错而过永远不会相等循环就变成了死循环。这是训练营里反复强调的一个坑我在初学时也踩过。3.2 空数组与单元素数组的极端场景当数组为空时len(s) - 1等于 -1left 初始化为 0循环条件0 -1不成立函数什么都不做直接返回逻辑正确。当数组只有一个元素时left 为 0right 为 0循环条件不成立函数返回。这个元素单独存在于数组中反转结果和原数组相同逻辑也正确。这两个极端场景的处理得益于循环条件的严谨设计。反过来说如果循环条件写的是while left right单元素数组就会进入循环执行一次自己和自己交换虽然结果不受影响但属于无意义的操作。相比之下while left right从语义上更精准地表达了“还有一对元素需要交换”这个状态。提示写完代码后随手用[]、[a]、[a, b]这三个最小用例做一次心算推演能帮你快速验证代码的正确性。这是一个成本极低但收益极高的测试习惯。3.3 通过实际提交整理的常见错误速查表错误类型错误写法错误后果正确写法索引越界right s.size()访问最后一个元素时越界报错right s.size() - 1死循环while left ! right偶数长度数组无限循环while left right无效交换while left right中间元素无意义地自交换while left right空间超限新建数组反向填充额外空间 O(n)不符合要求原地 swap 操作忘记移动指针交换后不更新 left/right死循环每次循环后 left、right--这张表是我在做训练营题目时自己总结的每次刷字符串类题目之前都会过一遍能有效避免低级错误。尤其是第五种“忘记移动指针”这个错误在紧张的手撕代码场景下特别容易发生一定要形成肌肉记忆。4. 复杂度分析为什么这道题是双指针思想的绝佳入门4.1 时间复杂度与空间复杂度的完整推导时间复杂度方面循环体内的所有操作——比较、交换、指针移动——都是常数时间操作即 O(1)。循环最多执行n / 2次n 是数组长度。所以总时间复杂度是 O(n/2) O(n)这是一个线性时间算法。无论输入规模怎样增长运行时间的增长趋势都是线性的。空间复杂度方面整个过程中没有申请与输入规模相关的额外空间。局部变量只有 left、right、temp如果用临时交换法它们占用固定的内存空间不随 n 变化。因此空间复杂度是 O(1)完全符合题目要求。这里补充一个理解O(n/2) 和 O(n) 在复杂度分析中是同一个量级常数系数会被省略。时间复杂度的核心意义在于描述增长趋势而非精确运行时间n 增长一倍运行时间大致增长一倍这就是线性复杂度。4.2 对比不同方案的复杂度差异如果把题目改成“允许使用额外空间”还有一个更简洁的 Python 写法class Solution: def reverseString(self, s: List[str]) - None: s.reverse()list.reverse()是 Python 的内置方法内部就是用双指针原地反转实现的时间复杂度 O(n)空间复杂度 O(1)。但 LeetCode 的判题系统不会因为你用了内置方法就宽松处理实际上大部分内置方法在底层也有空间开销只是对于这个题目而言它依然是合规的。另一种写法是切片赋值class Solution: def reverseString(self, s: List[str]) - None: s[:] s[::-1]s[::-1]会创建一个新列表然后切片赋值再拷贝回原列表。这个方法在功能上正确但空间复杂度是 O(n)不符合题目的空间要求。在训练营里我见到不少人用这个写法然后反映说“自己的代码一提交就超空间”。原因就在这虽然切片写起来非常 Pythonic但它确实违反了“原地修改”这一核心限制。实现方式时间复杂度空间复杂度是否符合题目要求双指针 临时变量O(n)O(1)符合双指针 swap 函数O(n)O(1)符合list.reverse()O(n)O(1)符合切片 s[:] s[::-1]O(n)O(n)不符合新建数组反向填充O(n)O(n)不符合这道题的价值就在于它用一道看似平平无奇的题目把“复杂度分析”这个抽象概念具象化了。当你真正理解为什么某个方案空间超限、某个方案可以通过时你才算是第一次把算法复杂度和实际问题挂上了钩。5. 从 344 延伸开反转字符串类型的系统方法论5.1 双指针技巧在后续题目中的复用模式LeetCode 344 只是字符串反转类问题的第一块基石。同一个双指针核心思想可以变形出一系列题目反转字符串 II要求每 2k 个字符反转前 k 个反转字符串中的单词 III要求反转每个单词但保持单词顺序反转字符串中的单词要求反转整个字符串里的单词顺序。这些题目看起来各不相同但底层都是同一个套路找到需要反转的区间然后用双指针在该区间内做首尾交换。区别只在于“区间怎么划分”这个前置逻辑不同。比如反转字符串 II核心是循环步长设为 2k然后对每一步的区间判断是否剩余字符够 k 个反转字符串中的单词 III核心是先按空格切分单词再对每个单词做区间反转。在训练营里掌握 344 的这个双指针模板之后我再做这些变体题的时候明显感觉顺畅了很多核心原因是我不再需要每次从零想“怎么反转一个区间”而是直接把模板套进去把注意力全部放在区间划分逻辑上。5.2 从字符数组到字符串语言特性对算法思维的影响还有一个值得思考的点为什么 LeetCode 344 用字符数组而不是直接用字符串作为输入因为在 Python、Java 这类语言中字符串是不可变对象没法直接原地修改。而字符数组是可变对象可以在原地址上修改元素。这个设计其实在提醒你算法题最终要落到语言的表达能力上。在 C 里你可以直接操作string因为 C 的string是可变的swap(s[i], s[j])可以直接作用于字符串。在 Python 里如果你真的拿到一个str想反转它只能生成一个新字符串因为底层对象不可变。理解了这一点你在做字符串相关题目时就能更快地判断“这个题在当前语言里能不能原地操作”以及“如果不能我的替代方案应该是什么”。这也是为什么训练营在讲字符串专题时会专门对比不同语言处理方式的差异。5.3 我的实操建议如何高效吸收这道题的价值针对这道题我给出三个实操建议都是自己在训练营里总结的经验。第一个建议至少用两种语言各写一遍。我自己的习惯是核心题目先写 Python 练逻辑再用 C 练细节。两种语言切换之间你会更清晰地感受到语言差异对写法的影响而不会把某个语言的特殊写法误当成算法的本质。第二个建议把上面提到的那张错误速查表抄下来贴在能看到的地方。刷题初期最多的错误不是思路问题而是边界条件、索引越界这类低级错误。反复核对这几项能显著提高一次提交通过率。第三个建议做完 344 之后立刻做一遍 541 反转字符串 II 和 151 反转字符串中的单词趁热打铁加深对双指针反转区间这一模板的印象。我在同一天连着做完这三道题之后对字符串反转类题目的掌握程度有了质的提升。第 8 天训练营的内容让我最大的收获不是这道题本身而是它带来的思维转变刷算法题不是为了“解出来”而是为了理解每一种解法背后的权衡。344 用一个看似最简单的题目把双指针、复杂度分析、边界条件、语言特性这四件事串了起来而这四件事几乎贯穿了整个算法训练营的后续课程。如果你也正在训练营里或者正准备开始系统刷算法题建议把 344 当成一道“例题”而非“作业题”来对待。不要满足于提交通过试着把它讲到别人也能听懂试着换一种语言重写试着把所有变体题的解法都统一到这个双指针模板下。这个过程带给你的进步远远超过刷十道简单题。