344. 反转字符串
题目描述
输入一个字符数组 s，它代表一个字符串。请把这个字符串倒过来。
必须直接在 s 上原地修改，不能再开一个新数组，额外空间只能是 O(1)。函数不需要返回值，评测会检查修改后的 s。
示例 1
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]
示例 2
输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
数据范围
1 <= s.length <= 10^5s[i]都是可打印的 ASCII 字符
解题思路
反转后，第 i 个字符与倒数第 i 个字符互换了位置。所以用两个指针：left 从开头出发，right 从末尾出发，每次交换 s[left] 和 s[right]，然后两个指针各向中间走一步。当 left 不再小于 right 时，所有对称位置都已交换完；长度为奇数时，中间那个字符保持不动。
为什么正确
s[0..left) 和 s(right..n-1] 已经是最终的反转结果，中间 s[left..right] 仍是原来的顺序；并且始终有 left + right = n - 1。
复杂度分析
时间 O(n)，共交换 ⌊n/2⌋ 次；额外空间 O(1)。
易错点
循环条件是 left < right。如果写成 left < n，过了中点会把已经交换好的字符又换回去，最后得到原数组。在 Python 里也不要写 s = s[::-1]，那只是让局部变量指向新列表，原数组没有改变。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
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 -= 1class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char t = s[left]; s[left] = s[right]; s[right] = t;
left++;
right--;
}
}
}class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0, right = (int)s.size() - 1;
while (left < right) {
swap(s[left], s[right]);
left++;
right--;
}
}
};func reverseString(s []byte) {
left, right := 0, len(s)-1
for left < right {
s[left], s[right] = s[right], s[left]
left++
right--
}
}var reverseString = function(s) {
let left = 0, right = s.length - 1;
while (left < right) {
[s[left], s[right]] = [s[right], s[left]];
left++;
right--;
}
};function reverseString(s: string[]): void {
let left = 0, right = s.length - 1;
while (left < right) {
[s[left], s[right]] = [s[right], s[left]];
left++;
right--;
}
}