刷 LeetCode 的朋友对第 189 题“轮转数组”应该都不陌生。题目描述只有一句话给定一个数组将数组中的元素向右轮转 k 个位置。难度只是中等但在我面试候选人的经历里这道题暴露出来的问题比很多 hard 题都多。有人写完暴力解法就交卷有人背过三次反转的答案却说不清为什么有效还有人把额外数组法写出了空间 O(1) 的错觉。今天我想把这道题的完整解法链条从头捋一遍重点聊每个方案背后的原理、边界细节以及面试里真正拉开差距的答法。1. 题目本质右移 k 步到底在做什么1.1 从一个具体例子看轮转规则先看题目的标准示例。nums [1,2,3,4,5,6,7]k 3轮转后的结果是[5,6,7,1,2,3,4]。很多人第一次做这道题时会把这个过程理解成“整体往右挪越界的补到左边”这个理解没错但它只描述了现象没有揭示规律。换个视角每一个元素的新位置其实只取决于它的原下标i和步长k。经过轮转后原来在i位置的元素会移动到(i k) mod n的位置其中n是数组长度。这个公式是整道题的核心。你后面看到的几种“聪明解法”本质上都是对这个公式的不同实现方式。验证一下上面例子i 0位置的元素 1移动后应该在(0 3) mod 7 3也就是新数组下标 3结果为[_,_,_,1,_,_,_]正确。i 4位置上的元素 5移动后应该在(4 3) mod 7 0也就是新数组第一位最终[5,6,7,1,2,3,4]也确实把 5 放到了第一位。这个公式建议做题前自己手推一遍理解越深后面看任何解法都越轻松。1.2 k 的范围是第一个大坑题目默认k是非负整数但并没有限制k必须小于数组长度。比如nums [1,2,3]k 5那就要轮转 5 步。如果不理解取模直接按k去搬一定越界。关键在于轮转n次之后数组会回到原样。右移 5 位和右移5 mod 3 2位结果完全一样。所以所有正解的第一步都是先做k % n。这个取模操作不是可有可无的优化而是保证后面所有逻辑成立的前提。我也犯过低级错误k 0或k恰好等于n时取模后k变成 0后面的循环直接跳过返回原数组这是正确行为但如果你忘记取模在k n时三次 reverse 会把数组反转后又反转回来看起来也是原数组但中间过程产生大量无效交换。1.3 左右轮转的对称关系LeetCode 这题是右旋但其实左旋和右旋是等价的左旋k位等于右旋n - k位。只要掌握了右旋左旋就是改一个参数的事。后面延伸到反转字符串中的单词、循环队列等场景方向不同但内核完全一样。2. 暴力解法为什么它只配当热身2.1 最直接的搬移实现暴力解法的思路非常朴素题目说向右轮转k次那我就一次一次地转。每一轮把数组最后一个元素暂存起来然后把前面所有元素往后挪一位最后把暂存元素放到开头。写成代码如下def rotate(nums, k): n len(nums) if n 0: return 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的情况下肉眼可见是对的。我第一次刷这道题时也是这么写的当时提交还通过了因为 LeetCode 的用例没把它卡到超时。但如果你在面试里写出这个版本大概率会被追问一句“时间复杂度是多少”。2.2 复杂度推导为什么 k 一大就完蛋每次右移一步需要把n - 1个元素往后搬这是一个 O(n) 的操作总共要搬k_eff步其中k_eff k mod n。所以总时间复杂度是 O(n × k_eff)。最坏情况下k_eff ≈ n整个算法退化成 O(n²)。O(n²) 在面试里基本等于不可接受。当n是 10 的 5 次方时10 的 10 次方的操作量在现代机器上也要几十秒到几分钟而 LeetCode 判题系统通常给的是 1 秒左右的限制。不过有趣的是当k非常小比如 1 或 2时暴力法的时间复杂度是 O(n)和最优解一样而且代码更简单、更好理解。所以它并不是百无一用只是适用场景极其有限。一些嵌入式场景或者固定步长为 1 的环形缓冲搬移确实够用。2.3 暴力法给我们的启发暴力解法虽然效率低但它是验证所有优化解法正确性的最好对照。我建议你写完任何高效解法之后都拿它当基准随机生成数组和多组k来对比结果。这一步在刷题阶段极其有用能帮你快速抓住实现细节里的 bug。接下来讲的三种解法我都会用暴力法做交叉验证。3. 额外数组法空间换清晰面试中最稳的答案3.1 索引映射公式的由来既然我们已经知道元素i要去的位置是(i k) mod n那最直接的做法就是开一个等长的额外数组遍历原数组把每个元素放到新数组的正确位置上最后再拷回来。这个过程叫桶式填入不需要任何花哨技巧。def rotate(nums, k): n len(nums) k % n ans [0] * n for i in range(n): ans[(i k) % n] nums[i] nums[:] ans这段代码的漂亮之处在于它是“声明式”的你直接描述了元素的最终归属不存在任何中间状态。可以对照检查i 0的元素放入ans[3]i 1的放入ans[4]……所有下标都不重复、不遗漏。这也从侧面验证了轮转是一个排列permutation源下标到目标下标是双射。3.2 一个非常隐蔽的 Python 细节上面代码最后一行是nums[:] ans而不是nums ans。这两个写法的区别是 Python 基础里最经典的引用 vs 赋值问题。函数内的nums ans只是把局部变量指向新列表调用方手里的原数组完全没变测试时你会看到 rotate 之后数组纹丝不动。而nums[:] ans是对原列表对象的切片赋值会在原地修改列表内容这才是判题时检查的东西。这个坑我在给新人做 code review 时反复强调。很多语言也有类似问题比如 Java 里如果你用nums ans同样只改了引用但数组是对象其实可以通过System.arraycopy或手动遍历来原地拷贝。跨语言做题时一定要搞清楚“按引用传递”的边界在哪里。3.3 空间 O(n) 算不算好答案额外数组法的时间复杂度是 O(n)空间复杂度 O(n)这是我心里“最标准的合格答案”也是面试中我会优先让候选人先写的方案。它最大的优点是正确性一目了然面试官不用费力读你的代码就能确认你理解题意。当然面试官大概率会追问“能不能把空间复杂度降到 O(1)”这时候你至少已经拿到了一个保底分。如果你一上来就写空间 O(1) 的解法但写错了反而可能让面试官对你的基础能力打问号。所以我的建议是答题顺序先额外数组再原地反转再环状替换。这样既有思路的层次感也能降低翻车风险。4. 原地反转法三次 reverse 背后的数学逻辑4.1 为什么“反转”这件事能解决轮转问题现在来到流传最广的解法先把整个数组反转再把前k个反转最后把剩下n - k个反转。代码很短但如果你只是背下来面试官多问一句“为什么”就卡住了。我用序列的方式解释一下。假设数组是A [a1, a2, ..., a(n-k), b1, b2, ..., b(k)]我们把它看成两段前n-k个元素是 A 段后k个元素是 B 段。右旋k位的结果是什么是把 B 段整体挪到开头A 段接在后面也就是[b1,...,b(k), a1,...,a(n-k)]。现在做三个反转整体反转把整个数组逆序于是 A 段内部逆序、B 段内部也逆序位置关系变成[B逆, A逆]。再把前k个元素当前在数组开头的 B 的逆序段反转B 逆序段又变回正序 B把后n-k个元素反转A 逆序段变回正序 A。最终得到[B, A]正好是我们要的轮转结果。这个思路的关键洞察是轮转的本质是“把数组切成两段并交换顺序”而 reverse 是一个天然 O(1) 额外空间的交换工具。整个过程只交换元素不需要额外数组。4.2 实现与边界细节def rotate(nums, k): n len(nums) k % n if k 0: return def reverse(start, end): while start end: nums[start], nums[end] nums[end], nums[start] start 1 end - 1 reverse(0, n - 1) reverse(0, k - 1) reverse(k, n - 1)几个容易出错的小点第二段反转的范围是[0, k-1]第三段是[k, n-1]注意k是分界点不要在边界上写错成k1。如果k取模后为 0直接 return避免执行无意义的整体反转后再次反转。reverse函数里的while用start end而不是start ! end后者在元素个数为偶数时会交叉越过虽然结果一样但语义上不如前者严谨也更容易在心里推导。4.3 为什么这个解法空间是 O(1)原地反转法除了几个临时变量外没有任何额外存储所以空间复杂度是 O(1)时间复杂度是 O(n)。每个元素恰好被交换两次整体反转一次分段反转一次。总计 O(n) 次交换。这里还有一个有意思的细节三次反转的总交换次数恒等于n次左右和k的大小基本无关。也就是说无论k是 1 还是n/2这个解法的耗时都差不多。这一点和暴力法完全不同也是面试官常拿来对比追问的点。实际跑 LeetCode 的数据量时这个解法耗时非常稳定。5. 环状替换法O(1) 空间的另一条路与经典陷阱5.1 每个元素只需移动一次额外数组法做了“先复制一份再放回去”的工作反转法每个元素交换两次。那有没有一种算法让每个元素只移动一次、而且不借助额外空间有就是环状替换cyclic replacement。思路是这样的从某个起点开始把当前位置的元素取出来放到它该去的位置(i k) % n再把那个位置上被挤出来的元素继续往后放一路沿着链条走直到回到起点。def rotate(nums, k): n len(nums) k % n if k 0: return count 0 start 0 while count n: cur start prev nums[cur] while True: nxt (cur k) % n nums[nxt], prev prev, nums[nxt] cur nxt count 1 if cur start: break start 15.2 环的个数是 gcd(n, k)这是最大的坑如果你直接把上面的双层循环写出来并且去掉count变量会踩一个非常隐蔽的坑当n和k不互质时从一个起点出发不会遍历完所有元素。举个例子n 6k 2。从索引 0 出发链条是 0 → 2 → 4 → 0只经过了 3 个位置从 1 出发链条是 1 → 3 → 5 → 1经过另外 3 个位置。也就是说总共存在gcd(6, 2) 2个独立的环你必须从多个起点开始处理才能覆盖整个数组。如果你只写了内层循环、没有count或 visited 控制那么外层从 0 循环到n-1时到start 2会把已经处理好的环重复跑一遍整个数组就全乱了。最常见的正确做法就是我上面的count版本用总移动次数卡死确保每个位置只被赋值一次。另一种做法是显式枚举起点for start in range(gcd(n, k))在内层回到起点时停止。两种都对但count版本逻辑更通用不用现场推导 gcd 公式。5.3 手动跑一遍 n6, k2 验证正确性为了让读者彻底放心我们手推一遍n6, k2的过程。初始数组[1,2,3,4,5,6]。第一环start0取出 1。nxt2把nums[2]的 3 挤出来nums[2]1cur2。nxt4把nums[4]的 5 挤出来nums[4]3cur4。nxt0nums[0]5回到起点环结束。此时数组[5,2,1,4,3,6]。第二环start1取出 2。nxt3把nums[3]的 4 挤出来nums[3]2cur3。nxt5把nums[5]的 6 挤出来nums[5]4cur5。nxt1nums[1]6回到起点环结束。此时数组[5,6,1,2,3,4]。最终结果与预期完全一致。这个解法在数据拷贝次数上是最少的n次赋值就完成了整个轮转。但它也是三种最优解法里最容易让读代码的人绕晕的面试时如果选择写它一定要配合清晰的注释和口头解释。6. 四种方案对比与现场答题策略6.1 复杂度对照解法时间复杂度空间复杂度原地修改代码难度面试推荐度暴力搬移O(n × k_eff)O(1)是低不推荐额外数组O(n)O(n)否低首选保底三次反转O(n)O(1)是中最推荐环状替换O(n)O(1)是高加分项从面试的角度我的建议是先用额外数组讲清楚思路、写出无 bug 版本然后主动提出“可以优化到 O(1)”再写三次反转。整个回答的脉络是从朴素到精巧面试官能看到你的思考过程而不是在背模板。6.2 现场答题时容易被追问的四个问题根据我实际面试别人的经验这道题最常见的追问有这么几个为什么k要先取模因为旋转n次回到原样k mod n才是有效步长。三次反转的时间复杂度是多少O(n)每个元素交换两次。环状替换里为什么外层循环可能不止一次因为独立的环个数是gcd(n, k)。如果k是负数怎么办按左旋处理等价于右旋n k位同样先取模。这里特别提醒千万不要在面试的时候只背代码不练表达。你可以在家对着镜子或者用手机录音练习把“为什么三次反转成立”用口语讲一遍。我见过不少候选人代码写对了但一被追问原理就支支吾吾最后评价反而低于预期。这也是为什么我一直强调做题时要把每个解法自己推导一遍。6.3 每种解法适合什么场景额外数组法在工程上其实并不差尤其当内存不是瓶颈时它的简洁性远比 O(1) 重要。三次反转法需要你确认数据确实允许原地修改有些业务场景里数组是共享的只读数据这时候就不能贪 O(1)。环状替换更适合数据拷贝成本很高的场景——比如元素是大型结构体每次赋值都要深拷贝那少拷一次是一次。真实工作中不存在“绝对最优”只有“当前约束下最合适”这一点面试官通常也很认可。7. 同源变体一道题带出一串题7.1 LeetCode 151反转字符串中的单词这道题可以先整体反转整个字符串再逐个反转每个单词。你会发现这和第 189 题的三次反转思路同出一源——都是利用 reverse 操作重组序列。区别只在于第二、三次反转的区间不是按固定k分割而是按空格切出的单词边界。刷完 189 再去做 151你会觉得轻松很多。类似的还有旋转字符串判断比如检查两个字符串是否互为旋转串把s1 s1拼起来再查子串就是利用了轮转后的序列仍然会出现在“加倍串”中的特性。7.2 标准库里的轮转实现很多语言的标准库其实自带旋转能力比如 C 的std::rotate。它默认是左旋接受三个迭代器参数底层正是环状替换的教科书实现。这也解释了为什么标准库源码里有一段专门处理 gcd 的逻辑因为要算出环的个数来启动多次替换。如果你把环状替换理解透了再去读这些源码会有豁然开朗的感觉。Python 里也可以用切片快速实现nums[:] nums[-k:] nums[:-k]但注意这本质上是额外数组法的语法糖空间复杂度依然是 O(n)适合快速写脚本不适合作为面试答案。7.3 业务中的真实轮转需求轮转数组并不是只出现在面试题里。我做音视频流处理时用过一个环形缓冲区里面就涉及对连续帧数据的整体平移游戏开发里做排行榜周榜刷新也经常要把上周数据滚动到历史位更常见的还有日志文件按天轮转log rotation。这些场景里189 题的三次反转法几乎可以原样迁移尤其当你处理的是百万级长度数组时O(n) 时间与 O(1) 空间的差异是非常直观的。最后说一点个人体会刷题这件事最忌讳的就是“这道题我见过”然后凭记忆抄一遍。LeetCode 189 是一个特别典型的“小题目、大原理”的例子四种解法正好覆盖了从暴力到声明式、从空间换时间到纯数学推导的完整思考路径。我建议你每个版本都亲手写一遍再用随机测试用例互相验证这样过一周后你仍然能自己推导出来而不是只记得一个答案。等你做到这一步这道题才算是真正吃透了。