LeetCode 344. 反转字符串
目录
题目描述
题意分析
输入是一个字符数组，要求把它的内容颠倒过来。函数没有返回值，调用方检查的是入参数组本身，所以所有修改都必须落在原数组上，返回一个新数组或新字符串等于什么也没做。
约束里最硬的一条是额外空间必须为 $O(1)$：不允许先复制一份再倒着拷回来，也不允许借助任何与 $n$ 同阶的容器。题目之所以给的是
char[]而不是String，正是为了让原地修改成为可能——Java 的字符串不可变，拿到String就只能造新对象。需要想到的性质是：反转后，下标
i上的字符去了下标n - 1 - i，反之亦然，两者互为对方的目的地。因此这是一组两两配对的位置关系，每一对只需要动一次手。边界上，空数组和长度为 1 的数组无需任何操作；长度为奇数时正中间那个字符的目的地就是它自己，同样不用动。
解法：左右双指针原地交换
核心思路
反转后，下标
i的字符应到达n - 1 - i。因此从数组两端开始，成对交换互为目标位置的字符，就能直接在原数组上完成反转，不需要额外数组。使用
left、right维护待处理区间。循环不变量是：[0, left)和(right, n - 1]已位于最终位置，[left, right]尚待处理。每轮交换两端并同时向内收缩；当left >= right时，待处理区间为空或只剩无需移动的中点，反转完成。
解题步骤
- 初始化
left = 0、right = s.length - 1。- 当
left < right时，交换s[left]与s[right]。- 执行
left++、right--，继续处理更内层的一对字符。- 指针相遇或交错时结束，函数直接修改原数组。
例如
['h','e','l','l','o']：先交换h/o得到o e l l h，再交换e/l得到o l l e h；此时指针在中点相遇，中间字符无需处理。
代码实现
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while (left < right) {
// 首尾对应位置交换，逐步收缩到中间。
char value = s[left];
s[left] = s[right];
s[right] = value;
left++;
right--;
}
}
}
func reverseString(s []byte) {
left := 0
right := len(s) - 1
for left < right {
// 原地交换两端字符，不额外创建数组。
s[left], s[right] = s[right], s[left]
left++
right--
}
}
复杂度分析
- 时间复杂度：$O(n)$，共交换 $\lfloor n/2 \rfloor$ 对字符。
- 空间复杂度：$O(1)$，只使用两个指针和一个临时字符。
关键点总结
i与n - 1 - i是一组对称位置，只需交换前一半。left < right同时适用于奇数和偶数长度，不需要处理中点特例。- 两个指针必须在交换后同时移动，否则会重复处理同一位置。
- 「原地」要求直接修改入参数组，不能返回新字符串替代。
易错点总结
right初始化为s.length：第一次访问就越界，合法末下标是s.length - 1。- Java 交换时连续覆盖而不保存临时值：
['a','b']会变成['b','b']。- 循环条件写成
left != right：偶数长度时两个指针会交错而永不相等。- 遍历完整数组并交换对称位置：每一对会被交换两次，最终恢复原样。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 151. 反转字符串中的单词 | 中等 | 需先清理多余空格，再整体反转加逐词反转，两次反转复合 |
| 186. 反转字符串中的单词 II | 中等 | 强制 $O(1)$ 空间的单词反转，本题的双指针是其内层子过程 |
| 345. 反转字符串中的元音字母 | 简单 | 双指针需各自跳过非元音字符，只交换满足条件的一对 |
| 541. 反转字符串 II | 简单 | 按 2k 分段并只反转每段前 k 个，考察分段边界的处理 |
| 557. 反转字符串中的单词 III | 简单 | 单词顺序不变、只反转每个单词内部，需先切分再逐段反转 |
| 剑指 Offer 58 - I. 翻转单词顺序 | 简单 | 与 151 同型，可用来对比语言内置切分与手写双指针的差异 |