写这道题解析之前先说说我自己的状态。最近跟着 LeetCode 热门 100 题重新刷了一遍基础数组题周赛 430 前后又把很多老题翻出来做发现轮转数组Rotate Array第 189 题是典型的看起来简单、写起来翻车题目。题目描述只有一句话把数组往右轮转 k 位。可你实际去提交暴力的循环移位一上大数组就直接超时去翻题解又发现额外数组法、三次反转法、环状替换法都是 O(n)反而不知道该记哪个。这篇就把三种 O(n) 解法摊开来讲不只给代码还把每一步为什么这么做、边界条件在哪里、工程上到底选哪种全部说清楚。适合正在刷热题 100 的读者也适合面试前想快速吃透这道题的人。1. 题目到底在考什么轮转数组的三个隐藏考点1.1 先回顾题目再看暴力解为什么撑不住原题输入是一个整数数组nums和一个非负整数k要求把数组整体向右轮转。比如nums [1,2,3,4,5,6,7]k 3结果应该是[5,6,7,1,2,3,4]。所谓轮转就是把最后 k 个元素搬到最前面前面剩下的元素依次后移所有元素保持原来的相对顺序。新手的第一反应通常是写双层循环外层跑 k 遍内层把整个数组整体后移一位最后一个元素放到开头。这个写法在k和n都很小的时候没问题但时间复杂度是 O(n*k)。一旦n 100000、k 50000要执行 50 亿次移动LeetCode 上直接超时。很多人这时候才意识到这道题真正在考的不是能不能实现而是能不能用线性时间、甚至原地完成。暴力解还有一个变种直接nums nums[n - k:] nums[:n - k]。Python 里这行代码能过测试但严格来说它创建了新列表不满足题目原地修改的要求。很多面试官会追问这一点后面我会专门说。1.2 三个隐藏考点这道题能在热题 100 里占一席之地绝不是因为它难而是因为它一次覆盖了三个基础能力索引与模运算轮转的本质是(i k) % n。理解了这个公式三种解法都能推导出来。原地修改题目明确要求空间复杂度尽量低。很多人写得出正解但写成返回新数组就不合格。边界处理k可能大于n可能是 0数组可能是空的。这些细节在真实工程里同样存在。这三个考点恰好对应了三种解法各自的侧重点。额外数组法直接体现模运算三次反转法体现的是局部反转保持顺序的思维环状替换法则把模运算玩到了极致。1.3 和爱吃香蕉的狒狒这类题的通病顺便说一句最近很多人刷到 073 爱吃香蕉的狒狒第一反应也是模拟吃香蕉每小时一根一根减。结果一提交就超时因为n和h的范围摆在那里暴力循环根本扛不住。轮转数组的暴力移位和它是一个毛病——题目越简单越要警惕第一反应是不是 O(n²) 级别的写法。刷题多了你会发现凡是数组原地操作的题基本就是在考你能不能跳出真的去移动每一个元素这个惯性。2. 解法一开新数组空间换时间的典型套路2.1 思路和正确性额外数组法是最直观的线性解法。我们开一个同样大小的新数组newNums遍历原数组的每个下标i把它放到新数组的(i k) % n位置上最后再把新数组内容拷贝回原数组。为什么是(i k) % n因为右移 k 位元素的新下标在原下标基础上加 k数组长度是 n越界后从头开始所以取模。这个公式是整个题目的灵魂后面所有解法都没离开它。以[1,2,3,4,5,6,7]、k3为例i0的 1 放到(03)%73处i1的 2 放到(13)%74处...i7的 7 放到(63)%72处。最后得到[5,6,7,1,2,3,4]完全正确。时间复杂度 O(n)空间复杂度 O(n)。2.2 Java 实现和两个常见错误用 Java 写就是public void rotate(int[] nums, int k) { int n nums.length; int[] newNums new int[n]; for (int i 0; i n; i) { newNums[(i k) % n] nums[i]; } // 注意这里必须拷贝回原数组 System.arraycopy(newNums, 0, nums, 0, n); }这里有两个常见错误我见过很多人在评论区踩第一个错误是写nums newNums。这在 Java 里只是把局部变量nums指向了新数组方法结束后原数组根本没变LeetCode 检查的还是原来的数组内容。必须用System.arraycopy或者 for 循环把元素一个个复制回去。第二个错误是忘了处理k可能大于n。如果k 10、n 7(i 10) % 7实际上是(i 3) % 7代码能正确运行因为取模运算自动把 10 折叠成 3 了。但如果你在别的实现里先写了k k % n这里其实可以先做一遍归一化逻辑更清晰。2.3 什么时候该选它在面试里额外数组法适合作为第一版答案提出。原因很简单正确性一目了然代码短面试官不会觉得你在绕弯子。更重要的是很多真实工程的数组操作场景并不禁止额外空间数据量也没到内存不够用的程度开一个新数组反而可读性最好。但你要主动说出它的缺点空间 O(n)。如果面试官追问能不能原地做就自然过渡到后面两种解法。把这个递进关系表演出来比闷头写三个答案更有说服力。3. 解法二三次反转为什么先整体后局部的顺序不能乱3.1 生活化类比切开两段再换位三次反转法是我个人最推荐优先掌握的解法因为它代码最短、空间 O(1)、实际运行还特别快。思路是三步反转整个数组反转前 k 个元素反转后 n - k 个元素。为什么这样能成用切段的思想看。假设数组要右移 k 位我们可以把原数组想象成两段前n - k个元素是段 A最后k个元素是段 B。轮转的结果就是要把A B变成B A并且 A、B 内部的相对顺序都不能变。整体反转一次数组变成reverse(B) reverse(A)两段的位置换了但各自顺序反了再分别反转 B 段和 A 段顺序又正回来。结果恰好是B A。这就是先整体后局部的原理——顺序不能乱也不能改成先局部后整体那样做出来是完全不同的结果。用[1,2,3,4,5,6,7]、k3验证一遍反转全部[7,6,5,4,3,2,1]反转前 3 个[5,6,7,4,3,2,1]反转后 4 个[5,6,7,1,2,3,4]。和题目期望完全一致。3.2 严格的数学表达如果你面试时需要把话说严谨可以这样表述设原数组为A B其中|A| n - k|B| k轮转目标是把A B变为B A。第一次反转reverse(A B) reverse(B) reverse(A)第二次反转前 k 个reverse(reverse(B)) reverse(A) B reverse(A)第三次反转后 n - k 个B reverse(reverse(A)) B A。得证。这个证明过程建议自己写一遍印象会深很多。我当年就是只记住了步骤没理解原理结果面试时被问到为什么这样反转是对的当场卡壳。3.3 Java 实现与细节public void rotate(int[] nums, int k) { int n nums.length; k k % n; // 关键先归一化 if (k 0) return; // k0 或者 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--; } }注意这里的三个细节第一k k % n必须放在最前面。否则k大于n时第二次反转的范围会越界。比如n 5、k 7直接反转[0, 6]就错了。第二反转函数用while (start end)而不是while (start end)。中间元素不需要交换用避免多余操作也防止start超过end的情况。第三三段反转分别对应 0 到 n-1、0 到 k-1、k 到 n-1。写的时候别把边界搞混尤其是k和n-k的区分。k-1好理解因为前 k 个元素的下标是 0 到 k-1。3.4 这个解法在真实机器上往往最快很多人以为三种方法都是 O(n)性能应该差不多。但我在本地压测过大量随机数组三次反转法通常是三种方案里最快的原因是它完全顺序访问数组对 CPU 缓存非常友好。额外数组法同样顺序访问但多了一次新数组的分配和一次拷贝环状替换法虽然也是 O(n)但每个元素都要算一次(current k) % n取模运算有除法开销而且访问模式是跳跃的缓存命中率低。这些常数因子在 LeetCode 的大数组测试用例里可能看不出来但在真实的高性能代码里是有体感的。所以在工程场景中如果必须原地修改、又要空间 O(1)我优先选三次反转。4. 解法三环状替换理解模运算与环数的底层逻辑4.1 沿着模运算的链条跳下去环状替换的思路和前面两种完全不同。我们不是整体搬移而是把数组当成一个环从某个位置出发每次跳 k 步把当前位置的元素放到 k 步之后的位置上同时保存被覆盖的元素继续往下跳。以[1,2,3,4,5,6,7]、k3为例从下标 0 出发1 放到下标 3原下标 3 的 4 被挤出来4 放到下标 6原下标 6 的 7 被挤出来7 放到下标 2原下标 2 的 3 被挤出来3 放到下标 5原下标 5 的 6 被挤出来6 放到下标 1原下标 1 的 2 被挤出来2 放到下标 4原下标 4 的 5 被挤出来5 放到下标 0刚好回到起点。走了一圈7 个元素全都移动到位。这就像一个沿着环传递物品的过程每到一个位置就把手里的旧值放下拿起新值继续走。4.2 为什么需要 gcd环数和环长的推导不是所有情况下一个环就能覆盖所有元素。比如n6、k2从 0 出发会得到0 - 2 - 4 - 0只覆盖了 3 个下标再回到 0 就循环了。剩下1 - 3 - 5 - 1还有另一个环。这里就引出一个关键问题到底有多少个环每个环多长设环的长度为 L。在环上跳 L 次后必须回到起点也就是L * k是 n 的倍数。满足这个条件的最小正 L用数学语言说就是让L * k第一次被 n 整除所以L n / gcd(n, k)其中gcd是最大公约数。环数等于总元素数除以每个环的长度环数 n / L gcd(n, k)所以n6, k2时gcd(6,2)2两个环n7, k3时gcd(7,3)1一个环。这就解释了为什么k和n互质时一个起点就能走完全部元素。4.3 计数法的 Java 实现知道了环数就可以从0到gcd(n,k)-1每个起点各走一个环。但更简洁的写法是不显式算gcd而是用一个计数器count记录已经移动了多少个元素移动满 n 个就停止这就是空间 O(1) 的计数法public void rotate(int[] nums, int k) { int n nums.length; k k % n; if (k 0) return; 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); } }这里用do-while而不是while是为了保证至少执行一次移动——即使只有一个元素也要把它放到应该在的位置。count n是外层终止条件移动满 n 个元素就说明所有位置都正确了不需要再开启新环。另一种写法是维护一个boolean[] visited标记每个下标是否已经移动过。这种写法更符合直觉但额外用了 O(n) 空间违背了环状替换想展示的原地 O(1)优势。面试时两种都能提重点要说清楚你选的这种为什么空间是 O(1)。4.4 一个容易被忽视的事实环状替换不一定快这里我想泼一盆冷水。很多题解把环状替换说成最优解理由是时间 O(n)、空间 O(1)听起来无懈可击。但在实际运行时它在三种解法里往往是最慢的原因有两个第一个是取模运算。每次移动都要算(current k) % n取模在 CPU 层面是除法操作比加减法慢一个量级。n 越大这个开销越明显。第二个是内存访问不连续。环状替换是跳着访问数组的跨越 k 步的访问模式会频繁打乱缓存行的预取逻辑。而三次反转法每次都从一段连续区间的两端向中间收缩访问模式是线性的缓存友好得多。所以正确的认识是环状替换的价值在于数学上优雅、空间上极致以及可以推广到按任意置换规则重新排列数组这类更复杂的场景。但如果你追求的是工程上的绝对性能三次反转法通常才是更好的选择。这个反直觉的结论我在很多技术群里提过不少人都表示实测确实如此。5. 你以为写了 O(n) 就完了边界条件才是真正的大坑5.1 k 大于数组长度的处理这是最容易翻车的点。假设n 5k 7右移 7 位和右移 2 位是等价的因为移动 5 位会回到原样。所以在任何解法的最前面都应该先执行k k % n。归一化之后k一定落在[0, n-1]区间后面所有边界判断都安全了。5.2 三种解法各自要额外注意的分支额外数组法k % n不写也能运行模运算本身会折叠但为了逻辑统一最好写上。三次反转法k % n之后一定要加if (k 0) return;。否则reverse(nums, 0, k-1)会变成reverse(nums, 0, -1)虽然start-1、end0时 while 不进循环不会报错但这是靠碰巧不执行来维持正确性面试官看到会皱眉。更危险的是某些语言里传-1下标会直接抛异常。环状替换法k % n之后同样判断k 0否则next (current k) % n虽然不会出错但count永远不会达到n外层循环会多跑很多轮逻辑上不合理。5.3 空数组和单元素数组nums []时任何取模运算都会因为除零报错所以要先判断nums.length 0直接返回。nums [1]时无论k是多少轮转结果都是它自己。k % n之后一定等于 0所以也直接返回。这类用例虽然在 LeetCode 上基本不出现但工程中的数据是真实的可能会传进来。5.4 如果要支持向左轮转怎么办LeetCode 原题只要求向右轮转但真实业务里可能要求向左。向左轮转 c 位等价于向右轮转n - (c % n)位。所以可以做一个统一的入口// direction 1 表示向右-1 表示向左 public void rotate(int[] nums, int k, int direction) { int n nums.length; if (n 0) return; if (direction 0) { k n - (k % n); } k k % n; // 后面统一走右转逻辑 }注意k可能取到n所以最后再取一次模。这个兼容写法在工程里很实用算法题里见过变种题也会用到。5.5 一套可以直接抄的测试用例不管用哪种解法提交前我都建议跑一遍这张表里的用例用例输入k预期输出空数组[]3[]单元素[1]5[1]k 等于 0[1,2,3]0[1,2,3]k 为 n 的倍数[1,2,3]6[1,2,3]k 小于 n[1,2,3,4]2[3,4,1,2]k 大于 n[1,2,3,4,5]7[4,5,1,2,3]全相同元素[7,7,7]2[7,7,7]全相同元素这个用例很多刷题文章不会写但在工程里很有意义——它能验证你的算法是否在元素值相同但位置不同时依然正确防止某些实现依赖值比较来跳步。5.6 面试官的追问链条这道题在面试里经常被当成一个由浅入深的经典追问链先写能跑的版本 → 你给额外数组法能不能不用额外空间→ 你给三次反转三次反转的正确性怎么证明→ 用 A、B 段的推导还有没有别的思路→ 你给环状替换环状替换为什么不会漏元素→ 用 gcd / count 解释。把这条链完整走下来面试官对你的评价会明显高于只会背题解的候选人。所以我不建议一上来就甩环状替换而是从最朴素的解法开始一步步展示你的思考过程。6. 从这道题到生产代码三种解法在工程场景中的取舍6.1 轮转思想不是算法题专属很多人刷完题就把代码丢进收藏夹其实轮转数组的思想在真实系统里出现频率极高。最典型的是环形缓冲区Ring Buffer比如消息队列的底层存储、日志采集系统的内存缓冲都依赖读写指针在数组里循环移动这个模型。指针位置的更新就是(pos offset) % capacity和你在这道题里写的下标公式一模一样。另一个场景是日志滚动保留。系统只保留最近 N 份日志文件新日志到了就要把最旧的覆盖掉。如果底层是固定大小的文件数组轮转更新本质上就是在一个长度为 N 的数组里做整体前移或者写指针循环移动。这时候你不可能每次拷贝整个数组更常见的做法是用写指针加模运算这就是环状替换思想的工程化落地。还有数据流上的滑动窗口、图像的像素行平移、缓存系统中热点数据的循环覆盖这些都是轮转的变体。所以这道题值得你花一个晚上彻底吃透它不是孤立的。6.2 真实工程里我一般怎么选如果是让我在生产代码里实现对数组的轮转我的默认顺序是这样的空间允许、可读性优先 → 额外数组法。新数组加System.arraycopy团队里任何人都能一眼看懂出错概率最低。大数组、内存敏感、必须原地 → 三次反转法。代码也不长性能最好缓存友好。环状替换 → 除非是要实现通用的按置换规则重排工具类否则我不会在普通业务里用它。它的正确性证明更绕边界条件更多后续维护者如果不懂 gcd 很容易改出 bug。这是很现实的考量。算法题追求的是在最严苛条件下仍然成立工程代码追求的是在大多数情况下正确、可读、可维护。两者不矛盾但侧重点不同。6.3 工程里的验证方式对拍与随机测试LeetCode 有官方测试用例工程上没有。如果你把轮转逻辑写进一个公共工具方法我建议至少做两层验证第一层是上面那张边界用例表保证空数组、单元素、k 大于 n 这些情况不炸。第二层是随机对拍。写一个简单的参照实现比如额外数组法然后用随机生成的数组和随机 k 值跑一百组对比断言两种实现的结果完全一致。这个思路在刷题时同样适用——你可以用最笨但最不容易错的版本当标准答案去验证你优化后的版本有没有隐藏 bug。对拍代码几十行就能写完但能省下大量试错时间。6.4 不要把算法题解法直接硬搬进代码评审最后想提醒一点LeetCode 的输入输出是固定函数签名工程里不是。真实代码里你要考虑几件事原数组是否允许被修改很多业务系统把数组只读你直接原地改会引发不可预知的副作用。是否要考虑线程安全原地反转在并发环境下如果被多个线程同时读取会看到中间态。额外数组法反而更安全因为新数组构造完成之前旧数组完全不会被改动。数据类型是否真的需要数组在 Java、Python 里很多时候用ArrayList、list配合切片操作更自然不必为了炫技而强行写三指针反转。这些不是算法能覆盖的但恰恰是工程实践指南里最值得你带走的部分。我个人刷这道题的体会是三种解法不要只挑一种记而是把三种都写一遍尤其是把推导过程写一遍。只看题解你三天后大概率忘了为什么反转两次能恢复顺序自己推一遍 A、B 段这个记忆能留很久。遇到面试聊到这道题你随手画两段示意面试官就知道你是真懂还是背题。轮转数组是个小题目但吃透它等于把模运算、原地算法、边界思维、工程选型这四个基础模块都过了一遍这笔账很划算。