输入#

整数数组 nums 和非负整数 k

输出#

原地修改 nums，将其向右轮转 k 步

约束条件#

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

进阶约束#

• 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 $O(1)$ 的 原地 算法解决这个问题吗？

示例1#

1
输入：nums = [1,2,3,4,5,6,7], k = 3
2
输出：[5,6,7,1,2,3,4]

解释：

1
向右轮转 1 步: [7,1,2,3,4,5,6]
2
向右轮转 2 步: [6,7,1,2,3,4,5]
3
向右轮转 3 步: [5,6,7,1,2,3,4]

示例2#

1
输入：nums = [-1,-100,3,99], k = 2
2
输出：[3,99,-1,-100]

解释：

1
向右轮转 1 步: [99,-1,-100,3]
2
向右轮转 2 步: [3,99,-1,-100]

从额外数组出发#

最简单的思路：创建一个新数组 ans，将 nums[i] 放到 ans[(i + k) % n] 的位置，最后把新数组拷贝回 nums：

1
class Solution:
2
    def rotate(self, nums: List[int], k: int) -> None:
3
        n = len(nums)
4
        k %= n                          # 处理 k >= n 的情况
5
        ans = [0] * n
6

7
        for i in range(n):
8
            ans[(i + k) % n] = nums[i]
9

10
        nums[:] = ans                   # 拷贝回原数组

⚠️ 注意：k %= n 这一行很关键。当 k >= n 时（如 k = 10, n = 7），轮转 k 步等价于轮转 k % n = 3 步。虽然不取模的话 (i + k) % n 也能算出正确位置，但轮转超过一整圈纯属浪费。

这里用 nums[:] = ans 而不是 nums = ans——前者修改列表的内容（原地替换），后者只是让局部变量 nums 指向新列表（不会影响函数外部的原数组）。

瓶颈分析：这个方法需要 $O(n)$ 的额外空间。$n \le 10^5$ 时，$10^5$ 个整数的数组大约占 800KB——可以通过，但进阶要求挑战 $O(1)$ 空间。

🧠 直觉理解：创建新数组就像搬家时先把所有家具搬到临时仓库，再按新布局搬回去——稳，但需要两倍的空间。能不能直接在原地”挪”家具？

三次反转法#

这是本题最优雅的解法。将 nums 向右轮转 k 步，等价于以下三步：

1. 反转整个数组——让末尾的 k 个元素跑到开头（此时是逆序的），开头的 n-k 个元素跑到末尾（同样逆序）
2. 反转前 k 个元素——恢复它们原本的顺序
3. 反转后 n-k 个元素——恢复它们原本的顺序

用数学语言描述：设原数组为 $A$，目标是将 $A$ 变为 $A[n-k:] + A[:n-k]$。注意到：

$\text{reverse}(A)[:k] = \text{reverse}(A[n-k:])$ $\text{reverse}(A)[k:] = \text{reverse}(A[:n-k])$

因此 $\text{reverse}(\text{reverse}(A)[:k]) + \text{reverse}(\text{reverse}(A)[k:]) = A[n-k:] + A[:n-k]$，恰好是目标结果。

1
class Solution:
2
    def rotate(self, nums: List[int], k: int) -> None:
3
        """
4
        Do not return anything, modify nums in-place instead.
5
        """
6
        k %= len(nums)
7
        nums.reverse()
8
        nums[:] = nums[:k][::-1] + nums[k:][::-1]

复杂度#

• 时间复杂度：$O(n)$。反转整个数组是 $O(n)$，两次切片反转分别是 $O(k)$ 和 $O(n-k)$，总复杂度 $O(n)$。
• 空间复杂度：$O(1)$（算法层面）。nums.reverse() 是原地操作。nums[:k][::-1] 会创建 $O(k)$ 的临时列表，nums[k:][::-1] 会创建 $O(n-k)$ 的临时列表，但这些临时对象在赋值完成后立即被 GC 回收。若面试官要求严格的 $O(1)$，见下方”代码优化”章节的手动反转版本。

手动实现子区间反转（严格的 $O(1)$ 空间）#

用户代码中 nums[:k][::-1] 虽然简洁，但切片 [::-1] 会创建临时列表。如果面试官追问空间复杂度，可以手动实现区间反转：

1
class Solution:
2
    def rotate(self, nums: List[int], k: int) -> None:
3
        n = len(nums)
4
        k %= n
5

6
        def reverse(l: int, r: int) -> None:
7
            """反转 nums[l:r]（左闭右开）"""
8
            r -= 1
9
            while l < r:
10
                nums[l], nums[r] = nums[r], nums[l]
11
                l += 1
12
                r -= 1
13

14
        reverse(0, n)       # 反转整个数组
15
        reverse(0, k)       # 反转前 k 个
16
        reverse(k, n)       # 反转后 n-k 个

这个版本没有任何额外数组分配，空间复杂度严格为 $O(1)$。reverse 函数使用双指针交换，每对元素交换一次，总共 $n$ 次交换。

切片反转 vs 手动反转#

两种写法都是正确的，选择取决于场景。日常刷题用第一种（够简洁），面试建议先写第一种，然后主动提一句”如果需要严格 $O(1)$，可以手动实现子区间反转”——这会让面试官觉得你对细节有掌控力。

向左轮转#

如果题目改为向左轮转 k 步，只需调整反转顺序：

1
# 向右轮转 k 步：整体反转 → 反转前 k → 反转后 n-k
2
reverse(0, n)
3
reverse(0, k)
4
reverse(k, n)
5

6
# 向左轮转 k 步：反转前 k → 反转后 n-k → 整体反转
7
reverse(0, k)
8
reverse(k, n)
9
reverse(0, n)

💡 小贴士：想不通为什么？“向右轮转 $k$ 步”等价于”向左轮转 $n-k$ 步”，把 $k$ 换成 $n-k$ 代入向右轮转的公式就清楚了。