Easy

题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 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^5
  • s[i] 都是 ASCII 码表中的可打印字符

解题思路

这是一道经典的双指针题目，核心思想是使用两个指针分别指向数组的首尾，然后不断交换对应位置的字符并向中间移动。

解题思路：

  1. 双指针法：设置左指针 left 指向数组开头，右指针 right 指向数组末尾
  2. 交换操作：交换 s[left] 和 s[right] 的值
  3. 指针移动：left 向右移动，right 向左移动
  4. 终止条件：当 left >= right 时停止，此时所有字符都已完成交换

这种方法的优势在于：

  • 时间复杂度 O(n)，只需遍历数组的一半
  • 空间复杂度 O(1)，满足题目要求的原地修改
  • 逻辑简单清晰，易于理解和实现

推荐解法：双指针法是最优解，既满足题目的空间限制，又具有最佳的时间效率。

代码实现

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

public class Solution {
    public void ReverseString(char[] s) {
        int left = 0, right = s.Length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]];
        left++;
        right--;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小说明
时间复杂度O(n)需要遍历数组的一半，n 为数组长度
空间复杂度O(1)只使用了常数个额外变量

相关题目