最近刷力扣刷到 189 题这道“轮转数组”算是数组章节里非常经典的题目了。说它经典不是因为难而是因为它几乎以一己之力把“一题多解”这件事讲明白了——暴力法、辅助数组、三次反转、循环替换每种做法的思路、复杂度、适用场景都能在这道题上充分展开。而且它稳稳地待在力扣热题 100 的榜单里很多刷题攻略、刷题顺序推荐都会把它放在数组入门到进阶之间是一道怎么绕都绕不开的题。我见过不少朋友第一次看到“轮转”这个词会懵一下其实把它理解成“把数组往右挪 k 步末尾的元素绕回到开头”就完全够了。这背后涉及的数组下标运算、取模、原地修改这些基本功恰恰是后面刷滑动窗口、双指针、循环队列等一系列题目都会反复用到的东西。这篇文章不打算只贴个答案。我会把这四种解法从头到尾拆开讲包括每种解法是怎么想出来的、复杂度到底怎么算、有哪些边界条件容易踩坑以及面试时如果被追问“还有没有更好的做法”该怎么接。刷题新手可以照着一步步实现已经刷过一遍的人也可以重点看看后面的常错点和变形扩展大概率会有点新收获。1. 题目到底在考什么轮转数组的核心谜面1.1 先花两分钟把题读透题目给你一个整数数组nums和一个非负整数k要求把数组整体向右轮转 k 步并且必须在原地修改返回值是void最后直接检查nums本身。举两个官方例子感受一下输入nums [1,2,3,4,5,6,7], k 3 输出[5,6,7,1,2,3,4] 输入nums [-1,-100,3,99], k 2 输出[3,99,-1,-100]第一个例子向右轮转 3 步就是把数组最后的5,6,7挪到最前面剩下的1,2,3,4顺次往后排。第二个例子 k2最后两个元素3,99挪到前面。再看一下约束条件这个很关键1 nums.length 10^5-2^31 nums[i] 2^31 - 10 k 10^5nums.length最大能到十万这就直接排除了那些时间复杂度在 O(n²) 级别的笨办法。k也可以很大这意味着你第一步就该想到取模。还有一个隐藏考点函数声明是void rotate(int[] nums, int k)如果你在函数里新建了一个数组并返回它那不好意思直接判错。这一点我在后文会专门展开。1.2 为什么这道题被当成“入门分水岭”力扣的题目难度标注里189 题是中等难度但说实话它的题目本身并不算难难的是你能不能把几种解法的思路都理清楚。我为什么说它是分水岭因为这道题考察的能力层次非常分明第一层能写出暴力法说明你理解了“轮转”这个动作本身知道每次挪一步是怎么发生的。第二层能想到辅助数组拷贝说明你具备最基础的空间换时间思想至少不笨。第三层能想到三次反转并解释清楚每一步反转的意义说明你对数组的“局部顺序”和“整体顺序”有感觉这类人刷后面的旋转矩阵、旋转链表会非常快。第四层能写出循环替换并且把count这个计数器讲明白说明你对置换、循环节、最大公约数这些数学概念有认知这在面试里属于加分项。很多刷题攻略会把这道题放在数组刷题路线的第十题左右前面一般是移除元素、删除有序数组中的重复项这类更基础的题。它不像“两数之和”那样一上来就考哈希表也不像“接雨水”那样一上来就考单调栈它就是老老实实考你数组操作的基本功但又不让你用太粗暴的方式糊弄过去。所以我说能把这道题的四种解法都吃透的人数组这一块的地基基本算打牢了。1.3 轮转的本质把“往后挪”翻译成下标运算我们先不着急写代码先把“轮转”这个动作在数学上到底是什么搞清楚。一个长度为 n 的数组向右轮转 k 步等价于把原来在下标i的元素移动到下标(i k) % n。反过来看最终结果里下标j位置的元素来自原来的下标(j - k n) % n。为什么是取模因为数组是线性的但轮转是循环的元素从末尾出去之后又从开头进来了这种“绕圈回头”的行为天然就是模运算。你可以把数组想象成一个循环队列头尾相接轮转 k 步就是在环上把每个元素往后拨 k 个位置。这样理解之后很多边界情况就顺理成章了比如 k 等于 n 时每个元素绕了一圈又回到原位数组不变k 大于 n 时实际上等效于 k 对 n 取模后的结果。这个“下标加上步数再取模”的视角是后面循环替换解法的基础也是面试官考这道题时最想听到你主动说出的观察。如果你能自己说出“本质上就是每个元素向右平移 k 位用模运算处理越界”那这道题的思路层就已经过关了。2. 四种解法逐个拆解从暴力到最优2.1 暴力法最容易想到也最容易超时暴力法的思路非常直白题目说向右轮转 k 步那我就一次轮转一步重复 k 次。每轮转一步先把最后一个元素保存下来然后把前面所有元素整体往后挪一位最后把保存的最后一个元素放到开头。class Solution { public void rotate(int[] nums, int k) { int n nums.length; k % n; for (int step 0; step k; step) { int last nums[n - 1]; for (int i n - 1; i 0; i--) { nums[i] nums[i - 1]; } nums[0] last; } } }这段代码逻辑完全正确但问题出在效率上。外层循环执行 k 次内层循环每次要移动 n-1 个元素总的时间复杂度是 O(n*k)。你想想约束条件n 最大十万k 最大十万极端情况下要执行 10^10 次操作在力扣上跑起来基本是超时警告没跑。所以暴力法在真实刷题场景里没有提交价值它的意义只在于帮你理解“轮转一步”到底做了什么。不过有个细节值得注意即使暴力法我也在一开始写了k % n。这不算优化只是为了防止 k 太大导致无意义的重复循环属于写任何解法都应该先做的一步。面试时如果你先写暴力法记得主动说一句“这个写法在数据量大时会超时我们继续优化”这是在展示你的复杂度意识。2.2 辅助数组空间换时间思路最直白既然每个元素的新位置是可以直接算出来的那我完全可以开一个新数组把每个元素放到它该去的位置最后再把新数组的值拷回原数组。这就是辅助数组法。class Solution { public void rotate(int[] nums, int k) { int n nums.length; int[] newArr new int[n]; for (int i 0; i n; i) { newArr[(i k) % n] nums[i]; } for (int i 0; i n; i) { nums[i] newArr[i]; } } }这个解法的时间复杂度是 O(n)只需要遍历一次数组空间复杂度是 O(n)因为额外开了一个等长的新数组。它的优点是无脑、不容易错适合在时间紧迫的情况下先写出来保底。但要注意这道题虽然要求原地修改却不禁止你用辅助空间所以辅助数组法在力扣上是能通过的。不过面试官看到这个解法大概率会追问一句“能不能不用额外空间”因为 O(n) 的空间在数据量大时并不理想。这时候你就需要引出下面这个解法了。我在实际辅导别人刷题时发现一个现象很多人写完辅助数组法就收手了觉得自己过了。这很可惜因为这道题真正的精华恰恰是下面的三次反转。辅助数组法只是正确解法里的“及格线”不是“优秀线”。2.3 三次反转面试官最想看到的解法三次反转法是一个极其优雅的原地解法时间复杂度 O(n)空间复杂度 O(1)也是这道题最经典的答案。它的操作只有三步反转整个数组反转前 k 个元素反转剩余 n-k 个元素。还是用[1,2,3,4,5,6,7], k3来走一遍原数组 [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]结果和题目要求完全一致。第一次看到这个解法的人都会觉得“这太巧了吧”但它背后的逻辑其实非常清楚。向右轮转 k 步本质上是把数组最后 k 个元素挪到最前面。反转整个数组后最后 k 个元素就跑到了最前面但它们的内部顺序是反的。所以接下来反转前 k 个元素把这部分的顺序正过来反转剩下的 n-k 个元素把其余部分的顺序也正过来。两次局部反转做完所有元素都回到了正确顺序。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 left, int right) { while (left right) { int temp nums[left]; nums[left] nums[right]; nums[right] temp; left; right--; } } }这个解法的好处不仅仅是省空间。它把“整体平移”这个看似需要大量数据搬移的操作拆解成了三次互相独立的反转每次反转都只做交换操作不涉及额外的数组拷贝。在工程上很多数组旋转、字符串旋转的问题都可以用这套思路套用。还有一个值得说的点反转法在面试时很好“讲”。你只需要在黑板上画一个数组标出反转区间三步下来结果就出来了非常直观。我后面第 3 章会专门用数学方式证明一下为什么这样做是对的这里先知道操作流程就行。2.4 循环替换数学味道最浓的原地解法如果你对“元素从 i 走到 (ik)%n”这个观察足够敏感你会想到另一种原地解法直接把每个元素放到它该去的位置被挤出来的元素继续放到它该去的位置这样沿着“链条”一个个放下去直到回到起点。这就是循环替换法。class Solution { public void rotate(int[] nums, int k) { int n nums.length; 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); } } }这里有一个非常容易踩坑的点如果你只从start0开始沿着链走可能并不能覆盖所有元素。举个例子nums [1,2,3,4,5,6]k 2下标变化是0 - 2 - 4 - 0这一圈只覆盖了三个元素剩下的1 - 3 - 5 - 1是另一条独立的环。所以外层循环必须从每个可能成为新环起点的下标开始尝试而count用来记录已经放置了多少个元素一旦放了 n 个就说明全部覆盖完了。这里面的数学背景是排列可以分解成若干个不相交的循环元素按(ik)%n移动构成的循环数量正好等于gcd(n, k)。比如 n6, k2最大公约数是 2所以有两条循环n5, k2最大公约数是 1就只有一条循环把五个元素全部串起来。循环替换法也是 O(n) 时间、O(1) 空间理论上和反转法同样优秀。但在实际面试中我一般建议优先说反转法因为循环替换的代码里do...while和count的关系需要花时间讲清楚而且一不留神就容易漏写count导致死循环。如果你能把循环替换法也写好并且解释清楚为什么外层还要继续遍历面试官会认为你对这个问题的理解已经超过绝大多数候选人了。我见过有些大厂面试官在反转法之后追问“还有没有别的原地解法”就是为了考察这层理解。3. 实操笔记完整实现与关键细节校验3.1 代码实现Java、Python、C 三种语言对照力扣上这道题支持多种语言我分别给出反转法的常用写法你在本地练习时可以直接对照。class Solution: def rotate(self, nums: List[int], k: int) - None: n len(nums) k % n def reverse(left: int, right: int) - None: 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)Python 的写法在思路上和 Java 完全一致唯一的差异是 Python 里可以用nums[left], nums[right] nums[right], nums[left]这种交换方式非常简洁。注意这里的reverse函数必须直接操作外层的nums不能新建局部变量再返回。class Solution { public: 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()); } };C 选手可以直接用 STL 里的reverse它接受迭代器区间写起来最省事。但要注意nums.begin() k指向的是第 k 个元素的位置区间是左闭右开所以不会越界前提是你已经对 k 取过模。我在实际练习时的习惯是先用 Java 写一遍不用辅助函数的版本再用 Python 写一遍最后用 C 的 STL 版本验证自己对迭代器区间的理解是否准确。三种语言各写一遍等于把同一个思路巩固了三遍。3.2 四种解法复杂度对比做题前先算这笔账解法时间复杂度空间复杂度是否原地适合场景暴力法O(n*k)O(1)是理解轮转动作入门用辅助数组O(n)O(n)否快速保底提交三次反转O(n)O(1)是面试首选答案循环替换O(n)O(1)是展示深度理解的加分项这个表格应该刻在脑子里。面试的时候你不仅要能说出每个解法的时间复杂度还要能解释为什么。比如暴力法是 O(n*k)因为每轮转一步要移动 n 个元素共做 k 次辅助数组是 O(n)因为只遍历一遍但额外开了一个数组反转法每次反转都是双指针扫描三次反转加起来总共只访问了数组常数次所以是 O(n)。还有一个小细节辅助数组法的空间复杂度虽然写的是 O(n)但严格来说力扣的判题系统只检查时间是否超限不检查空间峰值所以它能通过。但从解题者的自我要求来看能用 O(1) 空间解决的就不要用 O(n)。这种“在满足要求的前提下尽量优化资源”的意识在真实工程里比刷题本身更重要。3.3 k 值取模所有解法都绕不开的第一步几乎每一种解法的第一行都要写k % n。这一步很多人知道要做但不一定清楚如果不做会发生什么。我们用一个简单的场景推导假设nums [1,2,3]k 4实际结果应该是[3,1,2]因为轮转 3 步回到原数组再多转 1 步就等价于 k1。如果你不取模直接拿 k4 去算(i 4) % 3其实结果也是对的因为取模运算本身会把 4 变成 1。那为什么还要显式写这一步原因有两层。第一层是性能尤其是暴力法如果不取模外层循环会白白执行很多次无效操作第二层是代码安全后续的反转操作里k-1这个下标依赖 k 小于等于 n如果不取模k 大于 n 时就会出现数组越界。比如k 100000n 6k - 1 99999直接访问nums[99999]就崩了。我在本地测试的时候专门写了几组极端输入来验证取模的作用k0、kn、k2*n1、n1。这四组用例全部通过才算对取模这一步放心。这也是我要强调的刷题不是把样例过了就完事边界用例才是真正暴露问题的地方。3.4 反转法的严谨证明为什么三次反转一定正确光会写代码还不够这里我把反转法的正确性证明写出来面试被追问时你可以直接讲。设数组为 A长度为 n向右轮转 k 步。先把整个数组反转得到 A^R。A^R 的前 k 个元素恰好是 A 的最后 k 个元素的反转A^R 的后 n-k 个元素恰好是 A 的前 n-k 个元素的反转。接下来把前 k 个元素反转于是它们恢复成 A 中最后 k 个元素的原始顺序把后 n-k 个元素反转它们恢复成 A 中前 n-k 个元素的原始顺序。最终数组就变成了“原数组的最后 k 个元素 原数组的前 n-k 个元素”这正是向右轮转 k 步的定义。这个证明一句话总结就是整体反转把前后两段的位置对调两次局部反转分别把两段内部的顺序恢复。理解了这句话你甚至可以自己推导出向左轮转的版本向左轮转 k 步其实就是向右轮转 n-k 步也可以用三次反转完成。我在面试实战中就被问到过“如果要求向左呢”当场改参数其实很快但如果你没有从原理层面理解临时改就容易出错。3.5 循环替换法的代码走查一步一步带着你看循环替换法容易写错我带着你走一遍完整的执行过程。以nums [1,2,3,4,5,6],k 2为例start 0prev nums[0] 1进入 do 循环。current 0next (0 2) % 6 2把nums[2]原来的值 3 存到tempnums[2] 1prev 3current 2count 1。current 2next (2 2) % 6 4存下nums[4] 5nums[4] 3prev 5current 4count 2。current 4next (4 2) % 6 0存下nums[0] 1nums[0] 5prev 1current 0count 3。此时current start第一条环结束数组变成[5,2,1,4,3,6]。注意count 3小于 n所以外层循环继续start 1走第二条环。第二条环处理下标 1、3、5结束后count 6循环退出最终数组是[5,6,1,2,3,4]正确。我在给朋友讲这段时他问过一个很好的问题“为什么从 start0 走完一条环后下一个环一定是从 start1 开始直接从 0 的下一个没被访问过的下标开始不行吗”答案是因为从 0 开始不一定能走到所有下标但只要 count 没达到 n就说明还有元素没被放到正确位置而未被访问的下标中最小的一定适合作为新起点。这个结论依赖模运算的性质也是这道题里最“数学”的部分面试里能讲明白就是加分项。4. 常见错误与调试实录4.1 忘记对 k 取模越界和超时一起找上门这是出现频率最高的错误。我第一次提交这道题时就踩过这个坑当时写的暴力法没有取模本地测试用小数组没问题一提交直接超时。取模不仅仅是为了让 k 变小更是为了保证后续访问数组下标不越界。建议在所有解法的最前面都写上k % n把它当成类似“防御性编程”的习惯。如果你用的是 C 的 STL 反转写法没有取模时nums.begin() k可能直接越过end()这是未定义行为轻则运行出错重则本地都过不了。所以取模这一步真的写在哪里都不亏。4.2 反转区间边界写错off-by-one 的经典陷阱反转法的三个区间是[0, n-1]、[0, k-1]、[k, n-1]。最容易错的是第二个区间写成[0, k]第三个区间写成[k-1, n-1]。这种错误在 k 比较小的时候不太明显但一旦 k 恰好等于 n/2 或者接近 n结果就会乱掉。我的排查办法是给自己写一个简单的测试助手跑完反转法后再用辅助数组法的结果做对照。如果两边结果不一致就打印出每次反转后的数组一眼就能定位到哪一步的区间写错了。这比对着代码干想要快得多。4.3 Python 里“以为改了原数组其实没有”的坑Python 的写法有个非常隐蔽的坑。如果你写的是nums nums[-k:] nums[:-k]表面上看是在原地修改实际上你只是把局部变量nums重新绑定到了一个新的列表对象上函数外部的原列表压根没变。力扣判题时检查的仍然是传入的原始对象所以这种写法会导致结果不正确。正确的做法是用切片赋值nums[:] nums[-k:] nums[:-k]nums[:]这种写法才是真正把新列表的元素拷贝回原列表的内存区域。很多 Python 新手在这个问题上栽过跟头我在本地调试时也遇到过所以专门提醒一句判断一个操作是不是原地修改可以打印id(nums)看看函数前后是不是同一个对象。4.4 循环替换法漏写 count直接死循环循环替换法的外层循环条件是count n如果你忘了在 do 循环里给count加一外层循环永远不会退出程序直接卡死。另外还有一种错误是把count写在了 if 分支里导致某些情况下不计数同样会死循环。我的建议是写完循环替换法后先用小数组手算一遍确认 count 的递增节奏和元素放置的节奏完全一致。这道题考察的就是你对“每个元素都必须被移动且仅移动一次”这个事实的理解count 就是这句话的代码化身。4.5 高频错误速查表提交前对照检查错误类型典型表现解决方法忘记取模越界异常或暴力法超时开头加k % n反转区间 off-by-one结果局部顺序错乱用辅助数组法结果对照Python 重新绑定列表输出结果和原数组不一致用nums[:]切片赋值循环替换漏 count程序死循环do 循环内必须count函数里新建数组并返回力扣判错确认题目要求原地修改这张表是我自己刷题时踩过的坑汇总每次提交前扫一眼能避免绝大多数低级失误。5. 这道题在刷题路线里的位置与扩展变形5.1 力扣刷题顺序189 题放在哪一步最合适很多人问力扣刷题顺序到底怎么排我的建议是不要一上来就啃难题也不要只刷简单题。数组这一类里比较顺的路径是先做 27 移除元素、26 删除有序数组中的重复项这两道题帮你熟悉原地操作和双指针然后做 189 轮转数组它用到的下标运算和反转思想是这个阶段最重要的收获接下来可以刷 283 移动零、75 颜色分类进一步巩固原地数组操作再往后就可以尝试 15 三数之和这类需要排序加双指针的题目了。在这个路线里189 题起到的是一种“承上启下”的作用。它承上是因为它的暴力法和辅助数组法让你复习了基础数组操作它启下是因为反转法里“分段反转”的思路在后面的旋转矩阵、反转链表、字符串反转等问题里会反复出现。所以我不建议你用“暴力法过了就行”的态度对待它至少要把反转法练到闭着眼睛能写出来的程度。至于这道题算不算“简单题”我的看法是在掌握了反转法之后它确实配得上简单题的地位但如果你只能想到暴力法那它对你来说就是中等偏上的难度。力扣的难度标注只是一个参考真正的难度取决于你掌握了多少工具。5.2 相关变形题一道题带出一串题轮转的思想在力扣里有一系列亲戚题刷完 189 再去做它们会感觉非常亲切61 旋转链表把数组轮转换成了链表轮转思路是“先成环再断开”但本质上还是“找到分界点把后面一段挪到前面”。48 旋转图像二维矩阵顺时针旋转 90 度其实是先转置再逐行反转和三次反转法有异曲同工之妙。151 反转字符串中的单词先反转整个字符串再逐个单词反转这就是反转法的字符串版本。剑指 Offer 58 左旋转字符串把字符串前 n 个字符移到末尾等于向左轮转用三次反转可以直接解决。我建议你把这几道题放在一起刷每刷一道就想想“它和 189 有什么联系”。你会发现很多题的底层逻辑是相通的真正难的不是记下某一道题的答案而是理解这一类“先整体反转、再局部反转”的操作范式。5.3 面试实战建议被追问“还有更好的吗”怎么接这道题在面试里出现时面试官通常不会只满足于一个正确答案。多轮追问的常见套路大概是这样的第一轮让你写出任意解法。这时我会直接写反转法因为它最优雅省得后面再改。如果你想先写辅助数组法也没问题但写完要主动补一句“这里用了 O(n) 的空间可以优化到 O(1)”。第二轮问时间复杂度。回答“三次反转每段都是 O(n) 的扫描总体 O(n)空间 O(1)”。第三轮问 k 大于数组长度怎么办。回答“先对 k 取模因为轮转 n 次等于没轮转”。第四轮问“如果数组很大k 也很大性能瓶颈在哪”。这其实是在考你内存访问模式。反转法对数组的访问是连续的Cache 友好度高相比之下循环替换法的访问是跳着走的Cache 命中率低在极端大数组下反转法实际表现更好。这个点如果你能主动讲出来会非常加分。面试的时候还要注意一点先和面试官确认题目细节比如 k 是不是一定非负、数组能不能为空、要求原地还是可以开新数组。这些问题听起来像是在确认需求实际上是在展示你作为工程师的严谨性。我见过不少候选人上来就写代码结果漏掉了“原地修改”这个要求写了一个返回新数组的函数和题目南辕北辙。最后再分享一个我个人刷这道题的小习惯我会在本地写一个测试函数随机生成长度和 k用辅助数组法作为基准结果然后让反转法和循环替换法各自跑一遍三份结果互相验证。这种“用简单解法验证复杂解法”的思路不只是刷题有用写工程代码做重构的时候也是很好的保障手段。等你把 189 题刷到这个程度再回头看那些比你写得快的人你会发现你收获的其实不是一道题的解法而是一整套分析数组问题的方法。我自己第一次接触这道题的时候也是从暴力法开始一路踩过取模的坑、反转边界的坑最后才把四种解法都写顺。所以如果你现在正在为某个解法看不懂、写不出而烦躁那太正常了。别急着背答案拿支笔在纸上画一画数组每一步的变化画三遍你就能真正理解它。这道题值得你花一个晚上慢慢啃因为它值得。