轮转数组这道题只要在刷力扣 hot100几乎没理由绕开它。它在热题 100 的清单里排在第 10 位题库里的题号是 189难度标着中等但不少第一次做的人都会觉得它比看起来绕脑子。题目文字不多意思也很直白给定一个数组 nums 和一个整数 k把数组元素整体向右轮转 k 位末尾被挤出去的元素要一个个回到开头。乍一看就是个移动元素的小事但它背后同时牵扯到取模运算、原地修改、区间翻转这三块高频考点很多公司在二面、三面里也很喜欢挑其中的细节来追问。我自己刷这道题前前后后在模拟面试和笔试题里遇到过好几回所以这次干脆把它彻底拆开讲清楚从最直观的解法一路做到最优解再把最容易翻车的几个点挑明顺便聊两句后续可以怎么延伸。不管你是刚入门准备找刷题手感还是马上要面试想系统过一轮热题这篇都可以直接拿来当参考。1. 题目拆解先别急着写代码很多人看到这类题第一反应是上来就写循环觉得反正数组也不大移动就好。这个想法不能说错但如果你提前想清楚题目里的几个关键条件后面就能少走很多弯路。1.1 题面到底在说什么先看具体描述。输入是一个整数数组 nums 和一个非负整数 k要求把数组元素向右轮转 k 个位置。什么叫向右轮转说白了就是每个元素在数组里的下标统一往后移动 k 位如果越过了数组尾部就从头部重新进来。官方给的例子是输入nums [1,2,3,4,5,6,7]k 3输出[5,6,7,1,2,3,4]过程可以理解成先把 7 跑到开头然后 6、5 也依次跟进最后数组变成上面这个顺序。关键的隐藏条件往往不在示例里而在后面的进阶要求能不能只用 O(1) 的额外空间完成这意味着你不能随随便便开一个新数组去接住中间结果。这个进阶要求才是题目真正的门槛。如果允许额外开一个同样大小的数组这题难度可以直接降到入门级但一旦限制 O(1) 空间就必须在原地动刀这就会牵扯出接下来要讲的各种翻转和替换方案。另外k 的取值也没说一定小于数组长度k 可能是 100数组长度才 7这时候你必须意识到要先对 k 做取模处理否则后面写的所有边界都会乱套。1.2 大多数人第一反应的暴力方案先把最容易想到的方案过一遍。既然要让元素向右轮转 k 次那我就模拟 k 次每次把最后一个元素弹出其他元素依次往右挪一位再把弹出的元素放到开头。用 Python 写出来大概是这个样子def rotate(nums, k): n len(nums) k % n for _ in range(k): temp nums[-1] for i in range(n - 1, 0, -1): nums[i] nums[i - 1] nums[0] temp这段代码在逻辑上没有错循环一次就能让数组右移一位重复 k 次就完成了。但问题在于时间复杂度内层循环每次要移动 n 个元素外层要执行 k 次整体是 O(n*k)。当 n 是 10 万、k 是 10 万这种规模时实际要执行 100 亿次操作超时几乎是必然的。打个比方这就像让一队人全部往后挪一个位置挪一次所有人都要动挪一万次所有人就要动一万次。只要有一步算错整个顺序就会乱而且越到后面越难肉眼排查。所以暴力法只适合理解题意不适合真的拿去提交更不适合在面试里作为最终答案。1.3 用额外数组“作弊”一下暴力法慢就慢在每次只挪一位。既然题目本质是让每个元素去一个新的位置那我为什么不直接算出来每个元素该去哪儿向右轮转 k 个位置原本下标 i 的元素最终会落到下标 (i k) % n 的位置上。于是可以开一个新数组把每个元素放到目标位置最后再把新数组的内容拷贝回原数组。def rotate(nums, k): n len(nums) new_arr [0] * n for i in range(n): new_arr[(i k) % n] nums[i] nums[:] new_arr这段代码的时间复杂度是 O(n)遍历一遍就搞定比暴力法快了不止一个量级。唯一的代价是额外空间 O(n)多了一个和原数组等长的数组。在真实工程里如果你的内存充足又不强制原地操作这种“空间换时间”的做法完全没问题甚至是最容易维护的写法。但在面试场景中面试官通常会追问一句“能不能不用额外数组”这就逼着你必须进入下一节要说的经典解法。另外要提醒一个细节Python 里函数内部如果写nums new_arr只会在函数栈里新绑定一个局部变量外面的数组原封不动必须像我上面那样通过切片赋值nums[:] new_arr才能真正修改原数组这个坑后面还会专门说。2. 面试官最想看的解法三次翻转如果只能记住一种解法那一定是三次翻转。它不需要额外数组代码短思路又能讲得很清楚是这道题在面试场景里的标准答案。2.1 三次翻转的核心想法先观察一个具体例子。nums [1, 2, 3, 4, 5]k 2向右轮转的结果是 [4, 5, 1, 2, 3]。你可以把这个结果拆成两段来看后面两个元素 [4, 5] 整体跑到最前面前面三个元素 [1, 2, 3] 整体退到后面。这个结构让我想到一个很经典的技巧如果想让数组的某一段顺序发生变化可以靠翻转来完成。我们先把整个数组翻转一遍得到 [5, 4, 3, 2, 1]。这时候再观察原本在末尾的 [4, 5] 已经跑到整个数组的前面去了只是它们内部的顺序反了原本在前面的 [1, 2, 3] 也已经到了后面同样顺序反了。所以接下来的事就很简单把前面 k 个元素再翻转一次让内部的顺序恢复再把剩下 n-k 个元素也翻转一次顺序同样恢复。最终得到 [4, 5, 1, 2, 3]。整个流程可以浓缩成一句口诀先整体翻转再翻转前 k 个再翻转剩下的。2.2 代码实现与讲解在 Python 里可以自己写一个双指针翻转函数代码很干净def rotate(nums, k): n len(nums) k % n def reverse(left, right): while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1 reverse(0, n - 1) reverse(0, k - 1) reverse(k, n - 1)使用 C 的话更简单标准库自带reverse只是区间是左闭右开很多人第一次写会在这里卡住void rotate(vectorint nums, int k) { int n nums.size(); k % n; reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() k); reverse(nums.begin() k, nums.end()); }Java 没有现成的数组反转方法需要手动写双指针class Solution { public void rotate(int[] nums, int k) { int n nums.length; k % n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } private void reverse(int[] nums, int l, int r) { while (l r) { int tmp nums[l]; nums[l] nums[r]; nums[r] tmp; l; r--; } } }不管用哪种语言第一步k % n都不能省。如果 k 恰好等于 n取模之后变成 0整体翻转一次再翻转回来结果跟原数组一样等于白忙活但也比直接拿 k 去划分区间导致越界好得多。2.3 复杂度与记忆口诀三次翻转的时间复杂度是 O(n)因为每次翻转都是线性遍历三次叠加起来还是 O(n)。空间复杂度 O(1)所有交换都在原数组上操作没有引入额外的数组结构。不过很多人在面试现场会答错复杂度理由是“翻转了三次不是应该 O(n) 吗”其实 O(n) 和 O(3n) 在渐近意义下是一样的常数可以直接忽略。你只需要说每个元素在三次翻转中各被交换一次总工作量是 3n所以时间 O(n)原地交换所以空间 O(1)。这个解法记起来有个小窍门别死背“整体-局部-局部”的顺序而是想清楚你为什么翻整体翻转是为了把需要搬到开头的元素整体搬到开头局部翻转两段是为了修正每段内部的倒序。理解了这个因果关系就算面试时紧张也能一步一步推出来。3. 进阶视角环状替换与向左轮转三次翻转原理简单也不占空间但它有个小瑕疵每个元素在三次翻转中都会被移动两次整体逻辑看着不是那么“直接”。如果面试官进一步问“能不能让每个元素只移动一次就到位”就要请出环状替换法了。3.1 为什么需要环状替换环状替换的思路是既然我已经知道每个元素最终要去的下标是 (i k) % n那就别绕弯子直接把当前元素放到目标位置同时把目标位置原来的元素接过来继续放到它该去的位置上。就像接力赛一样A 把位置让给 BB 把下一个位置让给 C一个接一个往下传。但这里有一个很隐蔽的问题如果 n 和 k 不互质元素并不会只走一圈就遍历完所有位置而是会分成好几个不相交的环。举个例子nums [1, 2, 3, 4, 5, 6]k 2。从下标 0 出发0 - 2 - 4 - 0这是一个环但如果按照这个路径走完你会发现下标 1、3、5 根本没被访问到。它们其实是另一个环1 - 3 - 5 - 1。如果用纯循环实现遇到第一个环结束后就跳回起点很容易漏掉后面的环因此必须记录到底已经移动了多少个元素。当移动次数达到 n 时说明所有位置都被正确填过了这时候无论当前停在什么地方都可以结束流程。3.2 环状替换的完整实现一个比较稳妥的实现是同时维护一个已移动元素计数器外层循环从不同的起点出发确保每个环都被处理到。def rotate(nums, k): n len(nums) k % n if k 0: return count 0 start 0 while count n: current start prev nums[start] while True: nxt (current k) % n nums[nxt], prev prev, nums[nxt] current nxt count 1 if current start: break start 1这里有一个容易写错的点交换表达式里的赋值顺序。上面用的是 Python 的元组交换写法nums[nxt], prev prev, nums[nxt]它等价于先把右侧的旧值保存下来再执行两侧的赋值。这段代码的每个环退出条件都是current start也就是说回到了出发的下标说明当前环已经全部处理完可以启动下一个环。你也可以用更数学的方式计算环的数量循环个数等于gcd(n, k)然后直接按这个数量来启动外层循环。gcd 方案更省去 count 计数但要额外懂一点数论知识用计数法的好处是写起来不用思考数学细节对大多数场景都够了。3.3 向左轮转怎么改有些题会把轮转方向反过来改成向左轮转 k 位。比如 [1, 2, 3, 4, 5] 向左轮转 2 位得到 [3, 4, 5, 1, 2]。你可以用之前的三次翻转套路只要把翻转区间换一下就行先整体翻转再翻转前 n-k 个最后翻转后 k 个。推导过程和向右轮转完全对称。还有一种更省事的方法向左轮转 k 位本质上等于向右轮转 n-k 位。所以把 k 先换算成k n - k % n再用同一个向右轮转的代码即可。这个等价关系很重要不只是应付代码还能帮你检查自己的实现。面试里如果碰到方向变体先想一步换算往往能让思路清晰很多。我自己在做这类题时习惯先把例子写在小黑板上手动走一遍向左和向右的差异再决定翻转区间比硬记口诀靠谱。4. 边界情况与各种踩坑实录这道题提交时最容易挂的不是主逻辑而是一些平时根本不会注意的边界输入。我把实际踩过的坑整理成一个清单每一条都能对应一次 WA 记录。4.1 边界值自查清单首先是空数组。如果 nums 的长度为 0任何翻转操作都会面临下标越界的问题好在这时候直接返回就行但代码里必须显式处理或者让取模逻辑天然避免无意义的操作。然后是长度为 1 的数组。不管 k 是多少结果都应该是原数组本身。如果你忘了先处理 n 为 1 的情况某些方案的reverse(0, k-1)在第 k 很大时依然可能出错所以k % n这步一定要在数组长度为 1 时保证不会做无谓翻转。k 0 的情况也同样关键。取模后 k 变成 0三次翻转会先整体翻转再翻转前 0 个元素再翻转剩下的整体看等于翻两次结果还是原数组。逻辑上没错但白白浪费时间如果是环状替换我一般会直接在开头加一个if k % n 0: return让代码跑得快一点也防止极端情况下的死循环风险。k 是 n 的整数倍也是高频考题。nums [1,2,3]k 3向右轮转 3 位等于又回到起点结果不变。这类用例测试的是你有没有处理取模很多人没取模直接拿 k 去切片或翻转一下子就崩了。我把这些边界整理成一个简单的表输入k预期输出关键检查点[]2[]空数组直接返回[5]3[5]单元素数组不越界[1,2,3]0[1,2,3]k0 时快速返回[1,2,3]3[1,2,3]k 是 n 的整数倍[1,2,3]100[3,1,2]k 很大时取模[1,2,3,4]2[3,4,1,2]标准用例在提交之前拿这张表逐项跑一遍基本能挡住八成的边界问题。4.2 语言差异造成的坑Python 玩家最常见的坑是用切片之后发现原数组没变。正确的切片写法是nums[:] nums[-k:] nums[:-k]注意是给整个切片重新赋值等于在原数组的内存上做覆盖操作。如果你写nums nums[-k:] nums[:-k]Python 会创建一个新列表并绑定到局部变量 nums 上函数返回后外部数组一个元素都没变。C 玩家容易在reverse的区间上翻车。reverse(first, last)的区间是左闭右开reverse(nums.begin(), nums.begin() k)表示反转的是 [0, k) 这个区间不包含第 k 个元素。这个区间写错了数组就会在某个局部出现莫名奇妙的乱序。Java 玩家要注意int[]是长度固定的数组没有类似Collections.reverse能直接作用于基本类型数组的现成方法只能自己写双指针。而且 Java 的 LeetCode 方法签名是void rotate(int[] nums, int k)你必须原地修改 nums不能新建 int[] 返回否则编译器直接报错。4.3 一个测试驱动的自查流程我自己的习惯是写完解法后不急着提交先花两分钟构造几组测试用例。第一组用题目自带的示例确认基本逻辑第二组用 k 大于 n 的情况专门检查取模第三组用 k 等于 n 的整数倍检查会不会绕回原点。如果跑出来的结果和预期不一致不要直接盯着整个数组看而是把每一步中间状态打印出来。比如三次翻转你就分别打印第一次翻转后、第二次翻转后、第三次翻转后的数组很快就能定位是哪个区间画错了。这个方法在调试环状替换时尤其好用因为它最容易出现环漏掉的问题打印每次移动的下标和值一眼就能看出有没有走满 n 个数。5. 从这道题延伸出去的刷题思路热题 100 的价值从来不是让你背下那 100 道题而是通过它们掌握一组通用套路。轮转数组虽然只是一道中等题但它身上的两个核心技巧可以迁移到很多地方。5.1 同一套路的兄弟题第一个技巧是“局部翻转”它最典型的兄弟题是翻转字符串里的单词。那道题常规做法就是先把整个字符串翻转再把每个单词内部翻转一次三步搞定和轮转数组的三次翻转几乎是同一个模子。想到这一层你以后再遇到类似的题就不会慌因为你知道这类题的通用解是先整体处理再局部修正。第二个技巧是“取模映射下标”。搜索旋转排序数组、寻找旋转数组的最小值这类题本质上都是数组在某个位置“断开”之后再拼接利用下标取模或二分边界来定位目标。轮转数组帮你建立了对旋转后数组结构的敏感度后面再做二分相关的变体会更快上手。链表方向也有类似的轮转题给定一个链表向右轮转 k 个位置。思路是先把链表首尾相连形成环再找到新的头部断开这跟数组的取模思路如出一辙只是操作对象从连续内存变成了节点指针。建议你在刷完数组版本后顺手把链表版本也做了形成对比记忆。5.2 我的复盘方法对我来说刷这道题最有价值的不是记住三次翻转的代码而是学习“先想暴力再想优化”的完整思路。面对任何数组操作题我都会先问三个问题可不可以开额外数组能不能原地做能不能通过翻转代替移动这三个问题过一遍基本就能把一道题的常见解法串起来。你还可以在复盘时把环状替换和三次翻转放在一起对比问自己为什么三次翻转更受欢迎。虽然两者复杂度一样但三次翻转更好理解、更不容易写错所以面试时优先用它环状替换则展示了你对下标映射的理解更深。能把两者都讲清楚才是真的吃透了这道题。最后分享一点我自己的体会。我第一次做这道题时也只会开新数组被问到“能不能 O(1) 空间”时愣了半天。后来把三次翻转的原理画在纸上走了一遍才彻底明白为什么整体翻转之后还要分段翻转。从那以后我看到任何“每个元素都要移动固定步数”的题目第一反应就是取模和翻转这个思维习惯帮我解决了不少看起来毫无头绪的变体题。你现在卡在这一题上也很正常照着上面的思路自己推一遍例子比背代码有用得多。轮转数组只是热题 100 里很普通的一题但它能教给你的东西远比“会做一题”要多。