LeetCode 344. 反转字符串
题目描述
题意分析
输入是可以修改的字符数组，需要将其中字符的排列顺序完全反转。原来位于下标
i的字符，最终应位于n - 1 - i；字符本身不改变，只调整位置。必须直接修改传入数组，额外空间只能为常数，函数无需返回新字符串。题目字符均为 ASCII 可打印字符，Java 按
char、Go 按字节交换即可。
解法：左右双指针原地交换
核心思路
[!blue]
首字符的目标是末尾，末字符的目标是开头，它们互为目标位置，所以一次交换便能同时放对两个字符。处理完这一对后，问题缩小为反转去掉两端的内部区间。
用
left、right包围尚未处理的区间。每轮开始时，区间外的字符都已位于最终位置；交换两端并让两个指针同时向内移动，就把这个性质继续保持到下一轮。当
left >= right时，不再有需要交换的字符对。偶数长度时两指针交错，全部字符都已经处理；奇数长度时两者相遇，中心字符的目标就是自身，不需要移动。Java 先用临时变量保存一端字符，再执行两次赋值，避免旧值被覆盖；Go 的多重赋值会先读取两端旧值。整个过程只交换原数组元素，不分配替代数组。
解题步骤
- 令
left = 0、right = n - 1。- 当
left < right时，交换两个下标处的字符。- 交换完成后同时执行
left++、right--，继续处理内层。- 指针相遇或交错后结束，调用者持有的原数组已经被反转。
代码实现
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)$，只使用两个指针和一个临时字符。
关键点总结
[!green]
i与n - 1 - i是一组对称位置，只需交换前一半。left < right同时适用于奇数和偶数长度，不需要处理中点特例。- 两个指针必须在交换后同时移动，否则会重复处理同一位置。
- 「原地」要求直接修改入参数组，不能返回新字符串替代。
易错点总结
[!yellow]
- 末尾下标是
s.length - 1，不能初始化为数组长度。- Java 连续覆盖两个位置而不保存旧值，会让两端变成相同字符，丢失原内容。
- 不能用
left != right作为继续条件，偶数长度时两指针会交错而不相等。- 遍历完整数组并交换对称位置会把每对字符交换两次，最终恢复原样。
- 将局部变量重新指向一个新数组，并没有完成对传入数组的原地修改。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 541. 反转字符串 II | 简单 | 把整串反转限制为每2k区间中的前k个字符，复用区间双指针。 |
| 186. 反转字符串中的单词 II | 中等 | 整体反转再逐词反转可以原地倒置单词顺序，本题是其中的基本操作。 |
| 补充题 203. 反转字符串 | 简单 | 都用左右指针交换字符；补充题返回新字符串，本题原地修改输入。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！