189. 轮转数组（Rotate Array）
频次 ★★★ · 难度 🟡 · 高频：美团/京东
题目
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例：
输入: 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]
思路
三次翻转法（最优解）：
- 翻转整个数组
- 翻转前
k个元素 - 翻转剩余部分
例如 [1,2,3,4,5,6,7], k=3：
- 翻转全部 →
[7,6,5,4,3,2,1] - 翻转前 3 个 →
[5,6,7,4,3,2,1] - 翻转后 4 个 →
[5,6,7,1,2,3,4]✓
注意 k 可能大于数组长度，需要先 k %= n。
代码
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}复杂度
- 时间：O(n) — 三次翻转，每个元素最多被交换 3 次
- 空间：O(1) — 原地翻转
边界条件
k == 0或k % n == 0：三次翻转分别是”全部翻转、翻转前 0 个（空操作）、再全部翻转回去”，等价于不变，结果正确。k > n：必须先k %= nums.length，否则第二步reverse(nums, 0, k-1)会数组越界。- 数组长度为 1：任何
k都不影响结果，k %= 1恒为 0，翻转操作全部是空操作。
变式
- 向左移动
k位而不是向右：等价于向右移动n - k位，套用同一套三次翻转模板即可。 - 用额外数组实现：
result[(i + k) % n] = nums[i]，思路更直观但需要 O(n) 额外空间，面试官通常会追问”能不能做到 O(1) 空间”引导到三次翻转解法。 - 环形数组的其他题目（如约瑟夫环、循环队列）也常借助”取模处理环绕”这个技巧。
易错点
- 忘记
k %= nums.length是最常见的 bug，k大于数组长度时会导致reverse传入非法区间。 - 三次翻转的顺序不能错：必须先整体翻转，再分别翻转两段；如果先翻转两段再整体翻转，得到的顺序是错的。
面试追问
- 三次翻转法的原理是什么，为什么它能work？ 整体翻转会让原本在末尾的 k 个元素跑到最前面，但顺序是反的；再分别翻转前 k 个和后 n-k 个，相当于把这两段内部的顺序”翻转回来”，两次局部翻转抵消了整体翻转带来的内部乱序，只保留了整体错位的效果。
- 除了三次翻转，还有别的 O(1) 空间解法吗？ 可以用”循环替换”（cyclic replacement）：从某个位置出发，把元素直接放到最终该在的位置，再把被覆盖的元素接着放，直到绕回起点；正确性依赖
gcd(n, k)决定环的个数，实现比三次翻转复杂，一般不作为首选答案。