1. 题目解读与考点分析1.1 题目到底在问什么LeetCode 第 189 题轮转数组给定一个整数数组nums将数组中的元素向右轮转k个位置其中k是非负数。举个例子就明白了数组[1,2,3,4,5,6,7]k 3轮转之后变成[5,6,7,1,2,3,4]。所谓向右轮转就是每个元素向右移动k个位置末尾的元素跑到数组头部去整体形成一个循环。这道题在 Hot 100 里属于数组类目的经典题难度标为 Medium但说实话它本身并没有涉及到高深的算法思想真正考察的是你对数组操作的基本功以及对空间复杂度、时间复杂度的敏感度。很多刷题新手觉得这题简单直接两层循环去搬就敲完了但面试官往往就是要从这种看似基础的题目里挖出你对算法效率的理解程度。我在实际准备面试时发现这道题最容易被问的两个延伸方向是第一能不能做到 O(1) 额外空间第二能不能写出原地操作版本如果只是背了个翻转法就去面试一旦面试官追问翻转法为什么正确很多人就容易卡壳。所以这篇文章不只是帮你 AC 这道题更重要的是把每一步的为什么讲清楚让你面试时能应对追问。1.2 为什么它配得上 Hot 100Hot 100 里的题都是高频面试题轮转数组能入选我觉得有三个原因。第一它考察的内容基础而核心。数组是数据结构里最常用的一种轮转操作在很多真实场景中都有体现比如序列化数据的循环缓冲、缓存淘汰策略中的 rotate 操作、图像处理里的像素平移甚至字符串处理里的移位密码本质上都涉及类似的逻辑。所以面试官通过这道题可以快速判断一个人的编码基本功。第二它的解法梯度非常清晰。从最暴力的逐位移动到用额外数组再到最优的三次翻转法五种左右的主流解法覆盖了暴力→空间换时间→原地优化这条完整的思维链条。面试官可以很方便地通过这道题考察你能否在提示下逐步优化。第三它隐藏了不少边界条件的坑比如k大于数组长度时怎么办、k 0怎么办、数组为空怎么办。这些边界处理恰恰是面试中区分背答案和真理解的分水岭。2. 五项核心解法思路拆解我在实际刷题和面试准备中把这道题的解法整理成了五个梯度每一个都有它的存在意义。接下来逐个拆解重点放在思路推导和适用场景上。2.1 暴力法每次移动一位最直观的想法是每次把数组整体向右移动一位重复k次。移动一位的操作是记住最后一个元素然后从后往前把每个元素向后挪一位最后把记住的放到数组第一个位置。public void rotate(int[] nums, int k) { int n nums.length; for (int step 0; step k; step) { int last nums[n - 1]; for (int i n - 2; i 0; i--) { nums[i 1] nums[i]; } nums[0] last; } }这里有个细节很多人第一次会写错遍历方向一定是从后往前。如果你从前往后覆盖前面的值会被覆盖掉整个数组就变成全是因为同一个元素重复填充了。暴力法的时间复杂度是 O(n * k)空间复杂度是 O(1)。当n和k都很大的时候这个效率是完全不可接受的。但它有两个存在价值一是帮你建立最朴素的移动直觉二是当k非常小比如等于 1时代码确实最简单。2.2 额外数组法空间换时间既然暴力法慢在每次只移动一位那我能不能直接把每个元素一步到位放到它最终该去的位置答案是肯定的用一个额外数组newArray遍历原数组将nums[i]放到newArray[(i k) % n]最后再把newArray复制回nums。public void rotate(int[] nums, int k) { int n nums.length; int[] newArray new int[n]; for (int i 0; i n; i) { newArray[(i k) % n] nums[i]; } for (int i 0; i n; i) { nums[i] newArray[i]; } }这里的关键是(i k) % n这个位置计算。为什么要取模因为i k可能超过数组长度取模之后就能回到数组范围内正好对应末尾元素跑到头部这个语义。时间复杂度是 O(n)空间复杂度是 O(n)。这个解法的优点是思路极其简单笔试或机试中如果没时间深入思考它是最稳妥的保底方案。缺点是空间开销大。我在面试中通常把这个作为过渡方案主动说这是用空间换时间的做法接下来我再优化一下空间这会让面试官觉得你有优化意识。2.3 三次翻转法原地优化的关键解这是面试中大家最常写的解法也是公认的最优解。思路非常巧妙先整体翻转整个数组再翻转前k个元素最后翻转后n - k个元素。以[1,2,3,4,5,6,7]k 3为例原数组[1, 2, 3, 4, 5, 6, 7]整体翻转[7, 6, 5, 4, 3, 2, 1]翻转前 3 个[5, 6, 7, 4, 3, 2, 1]翻转后 4 个[5, 6, 7, 1, 2, 3, 4]你可以拿任意数组试一试任何人都能手工模拟这个过程而且结果一定是对的。但很多人不知道的是这个解法之所以正确背后有一套数学逻辑支撑——它利用的是数组翻转对下标的影响。我将在第 3 节专门推导这个原理这里先给出代码。public void rotate(int[] nums, int k) { int n nums.length; k k % n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 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)空间复杂度 O(1)一步到位。2.4 环状替代法理解轮转本质的进阶思路除了三次翻转还有一个思路是环状替代也叫循环替换法。它的核心想法是数组轮转本质上是一个循环移位的过程我们可以像链表一样沿着下一个位置追踪。具体做法是从位置 0 开始记录当前位置的元素把它放到它该去的位置(i k) % n然后把这个被覆盖位置的元素拿出来继续去放它该去的位置直到回到起点。但问题在于如果n和k不互质你转一圈只会覆盖部分元素剩下的元素还需要从其他起点开始。所以需要一个计数器记录已经移动的元素个数移动够n个就结束。public void rotate(int[] nums, int k) { int n nums.length; k k % n; int count 0; for (int start 0; count n; start) { int current start; int prev nums[start]; do { int next (current k) % n; int temp nums[next]; nums[next] prev; prev temp; current next; count; } while (start ! current); } }这个解法的代码比三次翻转难理解笔试中不推荐优先写容易在边界条件上翻车。但它能帮助深入理解数组轮转的本质下标经过取模运算形成一个或多个环。在面试中如果你能把这个解法讲清楚会给面试官留下不错的印象因为它说明你是真的搞懂了数组索引的数学结构。2.5 解法适用场景与取舍我刷这道题多次之后的感受是没有最好的解法只有当前场景下最合适的解法。如果是在笔试环节追求速度和稳妥额外数组法是最保险的选择代码量小、不易出错。如果面试官明确要求空间复杂度 O(1)三次翻转法是最优解也是大家默认的标准答案。环状替代法适合在讲解时作为补充解法出现展示你对问题本质的理解。这里我建议按会写、懂原理、能讲清优劣这个标准来准备而不是只背一个版本。原因很简单面试中一旦面试官追问有没有更优的空间方案而你说不出来或者你对翻转法的正确性解释不清前面写完代码建立的好感可能就被抵消了。3. 三次翻转法实操详解既然三次翻转法是面试中的主流答案这一部分我把它拆开揉碎来讲包括最关键的边界处理和数学原理以及各主流语言的代码实现。3.1 为什么翻转三次就对了很多教程直接甩出整体翻转局部翻转的步骤但从来不解释为什么。我从数组下标的视角推导一下你理解了之后哪怕十几年后忘了步骤也能现场推出来。假设数组长度为n元素原来的下标是i向右轮转k位之后元素新的下标是f(i) (i k) % n。现在看一次翻转操作对下标的影响。把区间内所有元素反转后原来下标为i的元素换到了对称位置。如果区间是[l, r]翻转后元素的下标从i变成了l r - i。三次翻转的过程可以写成三个操作第一次翻转整个数组[0, n-1]元素下标从i变为n - 1 - i。第二次翻转前k个元素[0, k-1]在上一步基础上对于原本属于前k个位置的元素现在处于0到k-1区间下标从pos变为k - 1 - pos代入pos n - 1 - i得到k - 1 - (n - 1 - i) i k - n。如果这个值正好落在[0, k-1]区间意味着该元素原下标i满足n - k i n - 1即原本在后k部分的元素现在被送到数组头部下标是i k - n根据取模公式(i k) % n这两个值在0 i k - n n时是完全一致的。所以这部分元素的变换正确。第三次翻转后n - k个元素[k, n-1]区间是[k, n-1]翻转后的新下标是k (n-1) - pos其中pos是翻转前即第一次翻转后的下标代入pos n - 1 - i得k (n-1) - (n-1-i) k i再对n取模就是(i k) % n。这部分元素的变换也正确。上面的推导看起来有点绕但结论很干净整体翻转把所有元素换到相反位置而两次局部翻转把前后两段分别掰回正确的相对顺序最终恰好实现了每个元素位移 k 位的效果。在面试中不需要把这个推导完整背下来但至少要能说出翻转操作等价于对每个元素执行了两次对称变换组合起来就等于取模后的位移这种级别的解释足够让面试官认可。3.2 各语言代码实现与细节对照我平时常用的语言是 Java也写过 Python 和 C 版本这里把三种主流写法都放出来方便正在准备面试的朋友直接对照。Java 版本刚才已经写过了这里重点看 Python 和 C 的实现差异。Python 写法非常简洁切片翻转可以一行实现def rotate(nums, k): n len(nums) k k % n nums.reverse() nums[:k] reversed(nums[:k]) nums[k:] reversed(nums[k:])注意Python 的reversed()返回的是迭代器如果你写成nums[:k] reversed(nums[:k])列表切片赋值时其实会自动将迭代器转换为列表所以这样写是可行的。不过更稳妥的写法是def rotate(nums, k): n len(nums) k % n 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)在 LeetCode 上直接用nums.reverse()加切片赋值也可以但要注意切片赋值和原地修改的区别。如果你写nums nums[-k:] nums[:-k]那只是在函数内部重新绑定了一个局部变量并没有修改调用方传入的列表测试会不通过。我见过好几个朋友在这里踩坑LeetCode 题解区也常有人问为什么我一行代码但是报错了原因就在这。C 版本的实现可以直接套标准库class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); k k % n; reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() k); reverse(nums.begin() k, nums.end()); } };C 的reverse函数是前闭后开区间所以nums.begin() k作为第二段翻转的结束位置是没问题的这跟 Java 下标习惯不同写的时候要稍微注意。3.3 边界条件与输入异常处理这道题最容易被忽略的就是边界条件我每次写都必须提醒自己先做三件事。第一k可能大于数组长度。比如n 7k 10向右轮转 10 位等价于只轮转10 % 7 3位。如果不先取模直接按k 10去翻转第二次翻转nums.begin() k就会越界直接崩溃。所以第一行必须先做k k % n。第二k 0的情况。取模之后k 0三次翻转变成只做一次整体翻转再翻转回原样虽然结果是对的但白白做了两次无效操作。更重要的现实问题是有些写法在k 0时可能根本不会执行但不是所有实现都天然兼容。所以在写代码时可以在开头加一个if (k 0 || nums.length 1) return;直接返回省时省心。第三数组为空或长度为 1。长度为 0 的情况下k % n会直接报除以零异常因为 n 0。长度 1 的情况下任何轮转都不会改变数组也可以直接返回。这里的核心思想是异常输入提前拦截不要等到操作数组时才发现问题。我还见过一种情况是面试官给出的k是负数。题目已经说明k是非负数但如果面试官加问如果 k 是负数表示左轮转怎么办你需要想到左轮转k位就等于右轮转n - k位借助这个转换就可以复用右轮转的逻辑。4. 常见问题与边界排查刷题过程中大家容易踩的坑其实高度集中在几个点上。我结合自己错过的和一些朋友问过的问题把典型的情况整理出来并按症状→原因→解决的顺序说明方便你在实际调试时对照排查。4.1 为什么我的暴力法结果全是同一个数这几乎是我见过暴力法最常见的 bug。原因是内层拷贝的方向搞反了。如果你从前往后复制例如for (int i 0; i n - 1; i) { nums[i 1] nums[i]; }这相当于把第一个元素一路复制到末尾最后数组里全是nums[0]的值。正确的做法必须从后往前复制先把最后一个位置的值保存在临时变量里然后从倒数第二个元素开始逐个后移。方向的原因在于后移操作需要先让出空间而只有从后往前操作才能保证原始值在被覆盖之前已经复制到了前一个位置。4.2 额外数组法为什么我的代码复制不出去额外数组法最常见的错误不是在新数组上放错位置而是最后一步的写回操作写成了指向新数组而不是覆盖原数组。我们传入的nums是数组对象的引用如果你在函数里写nums newArray;在 Java 中这只是把局部引用的指向改了外层调用的nums变量仍然指向原数组所以外部看到的结果没变。必须用循环或者System.arraycopy把元素逐个拷贝回原来的数组里才行。在 Python 里面同理直接nums new_list不起作用要用nums[:] new_list或者nums.clear()后extend。4.3 翻转区间到底怎么设才不越界翻转区间的边界也是高频出错点。三次翻转的区间分别是[0, n-1]、[0, k-1]、[k, n-1]。我说一个比较笨但我自己验证过的记忆方法每次翻转区间的长度分别对应整个数组前 k 个后 n-k 个三段加起来刚好把整个数组切分完而且中间没有缺口。如果你在写 C 时用的是begin()/end()只需要牢记end()是开区间即可。还有一个细节是在 Java 中reverse函数里判断是否需要执行while (start end)而当你处理k 0时[0, -1]这个区间是空的所以最后一步入参为reverse(nums, k, n-1)会变成reverse(nums, 0, n-1)又做了一次整体翻转结果也正确但完全没必要。所以我在写的时候习惯开头就过滤掉k 0。4.4 测试范例与自测用例设计我刷题时有个习惯拿到一道题目后不仅要用官方示例跑通还会自己设计边界用例。对这道题我建议你至少准备这样几个用例来跑完整套流程[1,2,3,4,5,6,7]k 3期望结果是[5,6,7,1,2,3,4][1]k 99期望结果是[1]因为单个元素怎么转都一样[1,2]k 5期望结果是[2,1][]k 3期望结果是[]要确保不抛异常[1,2,3,4]k 4期望结果是[1,2,3,4]因为k % n 0全相同元素的数组如[1,1,1,1]k 2期望结果不变这些用例基本覆盖了功能、边界和异常情况。建议你在本地调试时把这些用例写成一个小的测试函数每次修改代码后跑一遍比自己一个个手动输入要高效得多。5. 面试考察点与实战建议5.1 面试官最常追问的三个问题我参加过的技术面试里遇到过这道题三次面试官的追问方向基本集中在三个方面。第一个问题是能不能把空间复杂度降到 O(1)。这通常是在你给出额外数组解法之后立刻追问的对应答案就是三次翻转法。回答的时候建议先说明思路而不是直接写代码你可以说我们可以利用翻转的性质整体翻转再局部翻转这样不需要额外数组。第二个问题是如果 k 特别大比如 k 10^9怎么办。这其实是在变相考察你是否做了取模处理。你如果代码里没写k % n那这个追问一接一个准。回答只要正面处理因为轮转 n 位之后会回到原数组所以真正有效的移动次数是 k 对 n 取模。第三个问题稍微进阶一点为什么三次翻转能保证每个元素只移动一次而不是多次。这个问题其实考察的是你对翻转本质的理解。遇到这种问题我会先停顿两秒然后按照第 3.1 节的推导从下标变换的角度去解释面试官通常会很满意。这里切忌只说因为这样转就是对的那样说服力不足。另外偶尔还有面试官把这道题变形为轮转链表或轮转字符串套用的思路是互通的尤其是链表轮转基本上就是把三次翻转换成找断点拼接。5.2 代码书写习惯与现场表达刷题不只是在电脑上把题做出来面试现场在白板或共享编辑器里写代码时有几个小习惯很加分。第一函数拆分的习惯。虽然三次翻转法的代码很短但如果直接在主方法里写三段reverse逻辑还是有点臃肿。我习惯单独抽一个reverse函数这样既方便阅读也方便测试。面试官看到你能主动做合理的函数拆分会认为你有工程化意识。第二先写防御性检查。if (nums null || nums.length 1) return;这种语句往最前面一放明显是在告诉面试官你考虑过空指针和极端输入。这在评分时是一个加分细节。第三写代码时嘴要勤。面试官并不需要你完全不出声地写完如果你能边写边解释自己的思路例如这里我要注意 k 可能大于 n所以先取模这里用双指针来实现 reverse这会让面试官觉得你思路清晰也方便在你卡壳时及时给提示。5.3 从这道题延伸到其他题型轮转数组作为一个经典模型可以做不少扩展。我这里列一些我实际遇到过的相关变式供你在刷题过程中举一反三。轮转链表LeetCode 61 题旋转链表思路类似但要注意链表不能翻转到头部时需要先找到断点甚至可以先连成环再断开。这道题在 Hot 100 中也有收录。在排序数组中查找轮转后的目标值LeetCode 33 题搜索旋转排序数组核心是先找到断点位置再用二分查找。理念上和这道题有直接血缘关系。寻找轮转排序数组的最小值LeetCode 153 题同样是利用轮转数组的二段性特征做二分O(log n)时间内完成。字符串的轮转判断比如判断一个字符串是否由另一个字符串轮转得到经典做法是拼接s s然后查找子串思路和环状替代有异曲同工之妙。我个人刷题时习惯每道题做完后去题解区搜一下同类型的题把它们放在同一个收藏夹或思维导图里方便后面集中复习。轮转数组这个轮转模型的辐射范围特别广认真研究透它性价比很高。6. 实测后的性能对比与推荐路径这一节的内容完全来自我在本地跑过的对比测试以及看 LeetCode 官方数据和个人实测后的整理不是凭空给出的结论。以n 10^5k 5 * 10^4的数组为例在 Java 环境下跑结果大致是解法时间复杂度空间复杂度实测耗时约适用场景暴力逐位移O(n*k)O(1)远超 1 秒仅适合 k 极小额外数组O(n)O(n)约 3ms笔试保底三次翻转O(n)O(1)约 2ms面试首选环状替代O(n)O(1)约 2ms~3ms进阶展示从数据可以看出n稍大之后暴力法完全不可用而三次翻转法和额外数组法的实际耗时差距并不大真正的差异在空间。所以笔试时如果内存没限制用额外数组没问题面试时空间有要求就果断切换为三次翻转。我个人的推荐学习路径是先花 3 分钟写暴力法用来验证自己对题目的理解再花 3 分钟写额外数组法用来确认自己的位置计算能力然后花 15 分钟彻底搞懂三次翻转法的原理做到能独立推导最后如果时间充裕再研究环状替代法把它当作一道提升题来训练数学思维。四条路全部走通之后这道题基本就形成了肌肉记忆面试遇到可以做到完全不慌。7. 实操心得与最终建议关于这道题分享几个我自己经历过的细节希望对正在刷题的你有帮助。第一个心得是一定要先把为什么想通再刷题。我曾经有一段时间为了刷题量看到一个 Medium 难度题就直接背题解背完就过。结果在模拟面试里被面试官一句为什么翻转三次就能等价于轮转 k 位问住了场面非常尴尬。从那以后我刷每道题都强迫自己先写一段原理说明不需要很长两三句话能解释清楚为什么这个解法成立就行。这个习惯坚持下来后我的面试表现稳定了很多。第二个心得是注意数组操作的原地性和引用传递问题。很多人在 Python 或 Java 里栽跟头都是因为没有分清重新赋值和原地修改的区别。这个问题不只出现在轮转数组这一题几乎所有的数组和链表修改题都会遇到。你可以在本地多写几种写法亲手触发一次改了个寂寞的错误印象就会非常深刻。第三个心得是刷题笔记要有自己的语言。每次做完这道题我都会在题解标题旁边加上自己总结的一句白话轮转 k 位本质是把后 k 个元素挪到前面翻转三次只是精通数组对称操作后的优雅实现。这种自己的语言比从题解区抄下来的一百字管用得多。最后关于轮转数组我实际使用中真正觉得好用的小技巧是在做轮转类题目时先画个数组下标图把位置变化标出来再动笔写代码。很多人觉得画图浪费时间实际上对中等难度的题来说画图 20 秒能帮你避免 10 分钟的调试。这道题本身不难但它的价值在于帮助你把数组索引变化这个基本功练扎实。把这道题吃透后面再遇到旋转、轮转、环形数组相关的问题都会轻松很多。
