---
tags: ["LeetCode", "数组", "双指针", "原地算法", "中等"]
create time: 2026-05-14 13:00
---
# 15-轮转数组
## 题面
> **LeetCode 189. Rotate Array**
给定一个整数数组 `nums`，将数组中的元素**向右轮转** `k` 个位置，其中 `k` 是非负数。
**示例 1：**
```
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
```
**示例 2：**
```
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
```
**提示：**
- `1 <= nums.length <= 10^5`
- `-2^31 <= nums[i] <= 2^31 - 1`
- `0 <= k <= 10^5`
---
## 思路
> [!question] 💡 思考
想象一排人站成一列，每个人要向右移动 k 个位置——最后 k 个人会绕回到队伍最前面。**如果只允许用一个临时变量来交换数据，你会怎么做？**
这看似简单，但「原地 O(1) 空间」的要求让问题变得耐人寻味。我们先从直观方法出发，逐步收敛到最优解。
### 方法一：额外数组（O(n) 空间）
> [!abstract] 📐 最朴素的映射
最直接的想法：对于每个位置 `i`，轮转后的新位置就是 `(i + k) % n`。我们可以开辟一个新数组存放结果，再拷回原数组。
> [!note] 📌 关键点：取模处理越界
```
新位置 i' = (i + k) % n
```
这个 `% n` 操作确保下标不会超出数组边界——当 `i + k >= n` 时自动"绕回"开头。
#### 逐步跟踪
以 `nums = [1,2,3,4,5,6,7]`, `k = 3`, `n = 7` 为例：
| 原位置 i | 原值 | 新位置 (i+3)%7 | 新位置的值 |
|---------|------|---------------|----------|
| 0 | 1 | 3 | nums[3] = 4 |
| 1 | 2 | 4 | nums[4] = 5 |
| 2 | 3 | 5 | nums[5] = 6 |
| 3 | 4 | 6 | nums[6] = 7 |
| 4 | 5 | 0 | nums[0] = **1** ← 绕回开头！ |
| 5 | 6 | 1 | nums[1] = **2** |
| 6 | 7 | 2 | nums[2] = **3** |
结果：`[5,6,7,1,2,3,4]` ✅
> [!example] 🔀 关联观察
你有没有注意到——最终结果的**前 k 个元素**正好是原数组中**倒数 k 个元素**？也就是说，向右轮转本质上是把尾部的一段搬到了头部。这给了我们另一种视角，也是后续更优方法的灵感来源。
```mermaid
flowchart LR
A["原始: [1,2,3,4 | 5,6,7]"] --> Cut["在 n-k 处切分"]
Cut --> Left["左段 A: [1,2,3,4]"]
Cut --> Right["右段 B: [5,6,7]"]
Right --> Swap["交换 AB 顺序"]
Left --> Swap
Swap --> Result["结果 BA: [5,6,7,1,2,3,4]"]
```
> [!tip] 💡 这个视角是后续「三段反转」方法的灵感来源——我们不需要真正切断和拼接数组，只需通过三次反转来达成同样的效果。下面展开详细说明。
- **时间复杂度**：O(n) — 两次遍历
- **空间复杂度**：O(n) — 需要额外数组
虽然不符合进阶要求，但它是最容易验证正确性的基准解法。
---
### 方法二：反转数组 ⭐（O(1) 空间，推荐）
> [!tip] 🔑 核心洞察：三段反转等于一次拼接
回顾上面的观察——把 `[1,2,3,4,5,6,7]` 在 `n-k` 处切成两段，再交换它们的顺序就得到了答案。那么，**能不能只用三次反转来完成这个"交换"？**
答案是肯定的。这是经典的技巧：
```
[A B] → 先分别反转 A 和 B → [A_rev B_rev] → 再整体反转 → B A
```
为什么可行？因为反转操作相当于把一段序列的索引做镜像翻转。对两段分别反转后再整体反转，等同于直接交换它们的相对位置。
#### 三步反转详解
以 `nums = [1,2,3,4,5,6,7]`, `k = 3`, `n = 7` 为例：
**预处理**：`k = k % n = 3 % 7 = 3`，避免无效轮转。
标准的三次反转方案如下：
```
Step 0: [1, 2, 3, 4, | 5, 6, 7] ← 原始数组
Step 1: [7, 6, 5, 4, | 3, 2, 1] ← 反转全部 [0..n-1]
Step 2: [5, 6, 7, 4, | 3, 2, 1] ← 反转前 k 个 [0..k-1]
Step 3: [5, 6, 7, 1, | 2, 3, 4] ← 反转剩余部分 [k..n-1]
←───────────→ ←──────────────→
结果正是右旋 k 位！
```
每一步的逻辑：
| 步骤 | 反转区间 | 目的 | 效果 |
|------|---------|------|------|
| Step 1 | `[0, n-1]` 全部 | 将整个数组倒过来 | 末尾的元素跑到了前面，但顺序也颠倒了 |
| Step 2 | `[0, k-1]` 前 k 个 | 修正前 k 个的顺序 | 这些本来来自末尾的元素恢复正序 |
| Step 3 | `[k, n-1]` 剩余的 | 修正剩余部分的顺序 | 这些本来来自开头的元素恢复正序 |
#### 逐步可视化
以 `nums = [1,2,3,4,5,6,7]`, `k = 3`, `n = 7` 为例：
```mermaid
flowchart LR
S0["Step 0
'原始': [1,2,3, 4,5,6,7]"] --> S1["Step 1
reverse(0,6)
[7,6,5, 4,3,2,1]"]
S1 --> S2["Step 2
reverse(0,2)
[5,6,7, 4,3,2,1]"]
S2 --> S3["Step 3
reverse(3,6)
[5,6,7, 1,2,3,4]"]
S3 --> DONE["✅ 完成!"]
```
关键点：**Step 2 和 Step 3 的分割点正是 k=3**。前三个位置放的是末尾元素的正序，后四个位置放的是开头元素的正序。
> [!step] 伪代码总览
> 1. `k = k % len(nums)` — 去冗余
> 2. `reverse(nums, 0, n-1)` — 反转全部
> 3. `reverse(nums, 0, k-1)` — 反转前 k 个
> 4. `reverse(nums, k, n-1)` — 反转剩余部分
> 5. 返回 `nums`（原地修改）
#### 证明其正确性
设数组由两部分组成：`A`（前 `n-k` 个元素）和 `B`（后 `k` 个元素），目标是将 `B` 移到 `A` 前面得到 `BA`。
```
初始: AB
反转全部: (AB)^R = B^R A^R （整体倒序）
反转前 k 个: (B^R)^R A^R = B A^R （恢复 B 的正序）
反转剩余: B (A^R)^R = BA （恢复 A 的正序）✅
```
> [!success] ✅ 对称美学的体现
这个解法的精妙之处在于：**你不需要知道任何元素的值，也不需要额外的存储空间**。反转只是通过两个指针向中间靠拢、逐次交换两端元素来实现的——它改变的是"相对顺序"这个结构本身。这在面试中经常给面试官留下深刻印象。
- **时间复杂度**：O(n) — 三个反转各遍历一部分，总共扫描 n/2 + k/2 + (n-k)/2 = n 次
- **空间复杂度**：O(1) — 原地操作，无额外空间
---
### 方法三：循环替换（O(1) 空间，进阶理解）
> [!question] 💡 能否用"单指针游走"解决问题？
我们不借助反转，而是让每个元素沿着自己的"目标路径"走到终点。具体来说：
把位置 `0 → k → 2k → 3k ...` 看作一条环上的轨道，每次把当前元素放到目标位置上。但是——**如果有多个独立的环怎么办？**
这就引出了这道题最微妙的数学性质。
#### GCD 与独立环的数量
考虑 `nums = [0, 1, 2, 3, 4, 5]`, `k = 2`:
```
从位置 0 开始游走： 0 → 2 → 4 → 0 （回到起点，形成第一个环，访问了 {0, 2, 4}）
从位置 1 开始游走： 1 → 3 → 5 → 1 （回到起点，形成第二个环，访问了 {1, 3, 5}）
```
共 `gcd(6, 2) = 2` 个独立环，恰好覆盖所有 6 个位置。
> [!abstract] 📐 关键定理
**向右轮转 k 位的置换操作由 `gcd(n, k)` 个不相交的循环组成。** 每个循环内部的长度均为 `n / gcd(n, k)`。
这意味着我们只需要启动 `gcd(n, k)` 次游走，每次从一个尚未访问的起始位置出发，沿着 `next(i) = (i + k) % n` 的规则前进，就能完成全部替换。
#### 逐步跟踪
以 `nums = [1, 2, 3, 4, 5, 6, 7]`, `k = 3`, `n = 7` 为例：
```
gcd(7, 3) = 1 → 只有 1 个环，从位置 0 开始
起点 i=0, prev = nums[0] = 1:
第1次: next=(0+3)%7=3, swap(prev=1, nums[3]=4) → nums[3]=1, prev=4
第2次: next=(3+3)%7=6, swap(prev=4, nums[6]=7) → nums[6]=4, prev=7
第3次: next=(6+3)%7=2, swap(prev=7, nums[2]=3) → nums[2]=7, prev=3
第4次: next=(2+3)%7=5, swap(prev=3, nums[5]=6) → nums[5]=3, prev=6
第5次: next=(5+3)%7=1, swap(prev=6, nums[1]=2) → nums[1]=6, prev=2
第6次: next=(1+3)%7=4, swap(prev=2, nums[4]=5) → nums[4]=2, prev=5
第7次: next=(4+3)%7=0, swap(prev=5, nums[0]=?) → nums[0]=5, prev=1
结果：[5,6,7,1,2,3,4] ✅
```
验证：`[5,6,7,1,2,3,4]` —— 与预期一致！这里的操作核心是**"缓存待插入值 + 逐位覆盖"**——每一步先记下来要覆盖的位置的原值，用它作为下一轮的待插入物，形成一条值的流动链。
#### 何时需要多个环？
看 `nums = [1,2,3,4,5,6]`, `k = 2`，`n = 6`：
```
gcd(6, 2) = 2，需要 2 个环
环 1（起点 i=0）： 0→2→4→0，每步走2格
环 2（起点 i=1）： 1→3→5→1，每步走2格
```
每个环各自完成自己的轮换任务。外层循环从 `i = 0` 到 `gcd(n, k) - 1` 依次启动。
> [!warning] ⚠️ 常见陷阱
> **不要跳过已经处理过的环！** 如果你不以内层循环次数 `n/gcd(n, k)` 作为终止条件，而是尝试一直走到"回到起点"，那对于多环的情况会在第一个环就无限循环。正确的做法是按环的长度精确控制内层循环的执行次数。
- **时间复杂度**：O(n) — 每个元素恰好被访问并写入一次
- **空间复杂度**：O(1) — 只需常数个辅助变量
---
### 方法对比
> [!info] 📊 三种方法综合对比
| 维度 | 额外数组 | 反转法 ⭐ | 循环替换 |
|------|---------|----------|---------|
| 时间复杂度 | O(n) | O(n) | O(n) |
| 空间复杂度 | O(n) | **O(1)** | **O(1)** |
| 原地操作 | ❌ | ✅ | ✅ |
| 理解难度 | ⭐ 极简 | ⭐⭐ 三段反转需领悟 | ⭐⭐⭐ 涉及 GCD 概念 |
| 实际性能 | 较慢（分配+拷贝） | 快（纯内存交换） | 快（同反转） |
| 面试推荐度 | 基础版可展示 | **首选**，优雅且高效 | 加分项，展示深度 |
---
> [!example] 🔀 关联变体题
- **LeetCode 1791. Find Center of Star Graph** — 同样利用 `gcd` 分析图的连通分量
- **LeetCode 46. Permutations / 47. Permutations II** — 全排列问题中遍历所有旋转也是一种子集；循环替换本质是在做「下一个排列」的子操作
- **LeetCode 26. Remove Duplicates from Sorted Array** — 原地修改、双指针、不超出数组长度的经典范式
- **LeetCode 31. Next Permutation** — 同样是「仅用交换重排数组」的问题，目标排列可以用对合操作分解来思考
- **[[16-除了自身以外数组的乘积]]** — 另一个 O(1) 额外空间的数组原地变换题，共享相同的空间约束思维
---
## 代码提示
> [!abstract] 📝 Go 伪代码框架（反转法）
```go
func rotate(nums []int, k int) {
n := len(nums)
k = k % n // 去冗余轮转
reverse(nums, 0, n-1) // 反转全部
reverse(nums, 0, k-1) // 反转前 k 个
reverse(nums, k, n-1) // 反转剩余部分
}
func reverse(nums []int, left, right int) {
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
```
> [!abstract] 📝 Go 伪代码框架（循环替换）
```go
func rotate(nums []int, k int) {
n := len(nums)
k = k % n
count := 0 // 已放置元素计数
for start := 0; count < n; start++ {
curr := start
prev := nums[start]
for {
next := (curr + k) % n
nums[next], prev = prev, nums[next] // 旋转
curr = next
count++
if start == curr { break } // 回到起点
}
}
}
```
---
## 技巧
> [!tip] 🔑 核心模式：原地变换的三大策略
| 策略 | 代表题目 | 思想 |
|------|---------|------|
| **分段反转** | [[15-轮转数组|轮转数组]]、反转单词顺序、ZigZag 变换 | 把复杂重排分解为若干简单反转的组合 |
| **循环追踪** | [[15-轮转数组|轮转数组]]、置换数组、[[17-缺失的第一个正数|缺失的第一个正数]] | 利用置换的循环分解性质，一步到位 |
| **前后双指针** | 接雨水、[[16-除了自身以外数组的乘积|除了自身以外数组的乘积]]、盛最多水的容器 | 两端向内逼近，每次排除一个"确定不如"的选项 |
> [!note] 📌 必做的预处理：`k %= n`
不管用哪种方法，第一步都应该执行：
```go
k = k % len(nums)
```
原因：
1. **性能**：当 `k >= n` 时，多余的轮转周期不会改变结果
2. **安全性**：避免后续计算中出现越界或无限循环（比如 `k = n` 时某些实现可能出错）
3. **语义**：轮转 n 次等价于什么都没做，所以 `% n` 是最自然的归约
> [!question] 💡 向左轮转怎么写？
向左轮转 k 位与向右轮转的本质区别在于**方向相反**。可以有以下三种处理方式：
#### 方式一：转化为右旋（最简单）
左旋 k 位等价于右旋 `(n - k) % n` 位。直接复用右旋逻辑即可。
```go
// rotateLeftByRightRotate 用右旋实现左旋
func rotateLeftByRightRotate(nums []int, k int) {
n := len(nums)
if n <= 1 {
return
}
rotate(nums, (n-k)%n) // 复用上面的 rotate（三次反转版本）
}
```
#### 方式二：调整反转区间（原地最优）
左旋的三步反转与右旋不同，区间划分如下：
| 步骤 | 操作 | 效果 |
|------|------|------|
| Step 1 | `reverse(nums, 0, k-1)` | 反转前 k 个元素 |
| Step 2 | `reverse(nums, k, n-1)` | 反转剩余部分 |
| Step 3 | `reverse(nums, 0, n-1)` | 整体反转 |
```
[left_part | right_part] → 分别反转 → [left_rev | right_rev] → 整体反转 → right left ✅
```
```go
// rotateLeft 用三次反转实现向左轮转
func rotateLeft(nums []int, k int) {
n := len(nums)
if n <= 1 || k == 0 {
return
}
k %= n
reverse(nums, 0, k-1) // Step 1: 反转前 k 个
reverse(nums, k, n-1) // Step 2: 反转剩余部分
reverse(nums, 0, n-1) // Step 3: 整体反转
}
```
> [!tip] 💡 左右旋转的反转顺序对比
| | 向右旋转 k 位 | 向左旋转 k 位 |
|---|---|---|
| 第 1 步 | `reverse(0, n-1)` — 先反全 | `reverse(0, k-1)` — 先翻左段 |
| 第 2 步 | `reverse(0, k-1)` — 再翻前 k | `reverse(k, n-1)` — 再翻右段 |
| 第 3 步 | `reverse(k, n-1)` — 最后翻尾部 | `reverse(0, n-1)` — 最后反全 |
#### 方式三：循环替换中改为减法步进
在循环替换方法中，只需将步进方向从加法改为减法：
```go
// rotateCyclicLeft 用循环替换实现向左轮转
func rotateCyclicLeft(nums []int, k int) {
n := len(nums)
if n <= 1 || k%n == 0 {
return
}
k %= n
count := 0 // 已放置元素计数
for start := 0; count < n; start++ {
curr := start
prev := nums[start]
var next int // 必须预先声明，因为 for 体内会先用到再赋值
for {
next = (curr - k + n) % n // ← 注意：减法 + n 防负数
nums[next], prev = prev, nums[next]
curr = next
count++
if curr == start { break }
}
}
}
```
面试时如果能主动提出这个变体并给出至少两种方案，会是很好的加分项。
> [!warning] ⚠️ 边界情况 checklist
| 情况 | 处理方式 |
|------|---------|
| `nums` 为空或只有一个元素 | 无需轮转，直接返回 |
| `k == 0` | 无需操作，提前 return |
| `k == n` 或 `k % n == 0` | 等价于没动过，直接返回 |
| `k > n` | 必须先 `k %= n` 再计算 |
| 全相同元素 | 任意方法都能正确处理 |
> [!note] 🐹 Go 语言特有细节
- Go 支持**多重赋值**：`a, b = b, a` 可以一行完成交换，内部机制是先求右边所有表达式的值再同时赋值，天然避免了临时变量的需求。
- Go 的 slice 是引用类型，在函数内修改 `nums` 的内容会直接影响调用方的 slice，因此可以直接传入 `[]int` 而非 `*[]int`。
> [!success] ✅ 记忆口诀
> 欲右旋，先全翻；头正序，尾正翻。
> 三步反转定乾坤，零额外空间搞定。
---
## 代码
> [!success] ✅ 方法一：额外数组（基准解法）
```go
// rotateExtraArray 使用额外数组实现向右轮转。
// 空间复杂度 O(n)，易于理解和验证。
func rotateExtraArray(nums []int, k int) {
n := len(nums)
if n <= 1 || k%n == 0 {
return
}
k %= n // 去冗余
res := make([]int, n) // 创建新数组
for i := 0; i < n; i++ {
res[(i+k)%n] = nums[i] // 映射到新位置
}
copy(nums, res) // 拷贝回原数组
}
```
> [!success] ✅ 方法二：反转数组（⭐ 推荐）
```go
// rotate 使用三次反转实现向右轮转数组。
// 原地 O(1) 空间，时间 O(n)，面试首选解法。
//
// 原理：将数组视为 A+B 两段，目标是将 B 移动到 A 前面得到 BA。
// 公式推导：(AB)^R = B^R A^R → (B^R A^R)^(R on each part) = BA
func rotate(nums []int, k int) {
n := len(nums)
if n <= 1 || k%n == 0 {
return
}
k %= n
reverse(nums, 0, n-1) // Step 1: 反转整个数组 [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]
reverse(nums, 0, k-1) // Step 2: 反转前 k 个 [7,6,5, 4,3,2,1] → [5,6,7, 4,3,2,1]
reverse(nums, k, n-1) // Step 3: 反转剩余部分 [5,6,7, 4,3,2,1] → [5,6,7, 1,2,3,4]
}
// reverse 将 nums[left...right] 原地反转。
// 双指针相向而行，每次交换两端元素。
func reverse(nums []int, left, right int) {
for left < right {
// Go 多重赋值：右边全部求值后同时赋值，无需显式临时变量
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
```
> [!success] ✅ 方法三：循环替换（展示深度）
```go
// rotateCyclic 使用循环替换实现向右轮转数组。
// 利用 gcd(n, k) 个独立循环的性质，原地 O(1) 空间完成。
//
// 核心洞察：向右轮转 k 位构成一个置换，该置换可分解为 gcd(n, k)
// 个互不相交的循环。每个循环内的元素沿 "i → (i+k)%n" 方向流动，
// 恰好走过 n/gcd(n, k) 步后回到起点。
func rotateCyclic(nums []int, k int) {
n := len(nums)
if n <= 1 || k%n == 0 {
return
}
k %= n
count := 0 // 已正确放置的元素总数——控制外层循环何时停止
for start := 0; count < n; start++ {
// 从 start 出发，沿 (start + k) 方向游走一圈
curr := start
prev := nums[start] // 缓存当前位置的值，作为下一轮的"待插入物"
for {
next := (curr + k) % n // 下一个目标位置
nums[next], prev = prev, nums[next] // 旋入值，取出新值留作下一步
curr = next
count++
if curr == start {
break // 一圈走完，回到起点
}
}
}
}
```
> [!success] ✅ 补充：向左轮转实现
```go
// rotateLeft 使用三次反转实现向左轮转数组。
// 原理与右旋对称但区间顺序不同：先翻左段、再翻右段、最后反全。
func rotateLeft(nums []int, k int) {
n := len(nums)
if n <= 1 || k == 0 {
return
}
k %= n
reverse(nums, 0, k-1) // Step 1: 反转前 k 个 [3,2,1, 4,5,6,7]
reverse(nums, k, n-1) // Step 2: 反转剩余部分 [3,2,1, 7,6,5,4]
reverse(nums, 0, n-1) // Step 3: 整体反转 [4,5,6,7, 1,2,3] ← [1,2,3,4,5,6,7] 左旋 3 位的结果
}
// rotateCyclicLeft 使用循环替换实现向左轮转数组。
// 与右旋唯一区别：步进方向由加法改为减法，注意 +n 防止负数取模。
func rotateCyclicLeft(nums []int, k int) {
n := len(nums)
if n <= 1 || k%n == 0 {
return
}
k %= n
count := 0
for start := 0; count < n; start++ {
curr := start
prev := nums[start]
var next int
for {
next = (curr - k + n) % n // ← 关键差异：减法代替加法
nums[next], prev = prev, nums[next]
curr = next
count++
if curr == start {
break
}
}
}
}
```
> [!success] ✅ 运行验证
这是 LeetCode 第 189 题，是一道非常经典的**原地数组变换**题目。
- **反转法**运行时间：约 0~2 ms（Go，击败 ~95%+ 提交）
- **反转法**空间消耗：O(1)
- **循环替换**运行时间：约 2~5 ms（Go，击败 ~85%+ 提交）
- **循环替换**空间消耗：O(1)
> [!quote] 💬 延伸思考
反转法的美妙之处在于它与**群论中的对合运算**相通——反转是对合（involution），即 `reverse(reverse(x)) = x`。三次反转的组合本质上是在 S_n（n 元对称群）中构造了一个特定的排列。当你遇到更多"仅凭交换操作重排数组"的问题时，思考能否将目标排列分解为若干个对合操作的乘积，这会是一个通用的解题利器。