刷 LeetCode 的人应该都遇到过这个题给你一个数组把元素向右轮转 k 个位置。比如[1,2,3,4,5,6,7]轮转 3 位结果是[5,6,7,1,2,3,4]。题目本身不难但解法套路很有意思。我第一次做的时候想的是新建一个数组把元素按新位置放进去时间 O(n)、空间 O(n)简单直接。后来看到别人用三步反转法原地翻转、不开额外数组代码短到惊人心里那叫一个后悔——这么优雅的思路怎么就没想到。这篇文章就把三步反转法彻底讲透从问题拆解、数学原理、代码实现到避坑经验一次说清。适合刚开始刷题的朋友、准备算法面试的开发者以及想优化数组操作性能的工程场景。看完你不仅能写对这道题还能举一反三处理左旋、字符串反转、链表旋转这类变体。1. 问题拆解轮转数组到底在考什么1.1 先搞清楚题目的输入输出轮转数组的标准描述是这样给定一个数组nums将数组中的元素向右轮转k个位置其中k是非负数。要求原地修改数组不开辟额外数组空间。注意几个细节轮转是循环的元素从尾部“溢出”后会从头部重新进入。比如数组长度是 7k 是 3最后的 3 个元素会移到最前面。k可以比数组长度大。如果k是 10数组长度是 7那实际效果等同于轮转 3 位因为 10 除以 7 余 3。这个“取余”的细节很多新手会漏掉。要求原地修改意味着你返回的结果必须直接体现在传入的数组上不能 return 一个新数组就完事。LeetCode 189 题就是用返回值来判定的你如果只返回新数组判题系统直接报错。这道题考的核心并不只是“你能不能写出结果”而是三点是否理解循环位移的本质是否能控制额外空间复杂度到 O(1)以及边界情况处理是否严谨。面试里它经常作为热身题出现考察候选人写代码的基本功和暴力解之外的优化意识。1.2 三种主流解法的思路对比我先梳理一下常见的解法方便你建立全局认知。暴力法是每次把最后一个元素临时存下来然后所有元素往后移一位再把临时元素放到开头。重复 k 次时间复杂度 O(n*k)额外空间 O(1)。当 n 和 k 都很大时这个解法会超时只适合用来理解轮转的过程。额外数组法是开一个长度相同的新数组把每个元素放到(i k) % n的位置然后把新数组拷回原数组。时间 O(n)空间 O(n)。这是最直觉的写法代码简单也不容易出错但不符合“原地修改”的要求。强行拷回原数组其实也开了临时空间很多面试官会追问一句“能不能 O(1) 空间”。环状替换法是沿着索引的循环链移动元素从起点开始把当前位置的元素搬到(i k) % n的位置再接着处理那个被覆盖掉的位置直到回到起点然后移动到下一个起点继续。时间 O(n)空间 O(1)但实现的细节多容易在“循环链的起点数量”上栽跟头。三步反转法就是这篇文章的主角。它用三次原地反转完成轮转时间 O(n)空间 O(1)代码量最少逻辑也最好记。我把四种方案的对比整理成了一张表方便你面试的时候快速讲出区别。解法时间复杂度空间复杂度是否原地代码量记忆难度暴力法O(n*k)O(1)是少低额外数组O(n)O(n)否中低环状替换O(n)O(1)是多高三步反转O(n)O(1)是最少中低1.3 为什么偏偏是三步反转法原因很简单它在时间复杂度和空间复杂度上都达到最优同时思路直观代码不容易写错。面试场景下你写出暴力法只能证明你懂基本操作写出额外数组法会被追问空间优化而三步反转法几乎是一步到位直接展示了你对数组操作的敏感性。另一个原因是反转法具有很强的通用性。字符串反转、部分区间反转、链表旋转本质上都是同一套“区间操作”思想。把三步反转法吃透你等于掌握了一类题型的方法论而不是孤零零的一道题。我自己做算法题的经验是遇到数组类问题先想能不能用“反转”“交换”“双指针”这几个基础动作组合出优雅解法而不是一上来就开新数组。三步反转法就是“基础动作组合”的经典案例。2. 三步反转法的核心原理一次看懂为什么成立2.1 反转操作的数学性质理解三步反转首先要理解反转reverse这个操作本身的数学性质。反转一个区间就是把区间内元素的顺序完全倒过来。[1,2,3,4,5]反转后变成[5,4,3,2,1]。反转操作有一个非常重要的性质连续做两次反转等于什么都不做。一个区间反转后再反转一次元素顺序会恢复原样。这在数学上叫对合involution简单说就是“反转是它自己的逆操作”。这个性质看起来简单但它是三步反转法成立的基石。你把这个性质记住后面推导整个过程就非常顺。2.2 用分块视角证明三步反转我把推导过程写成数学公式的样式你耐心看一遍就会彻底理解。假设数组长度为 n需要右旋 k 位。我们可以把原数组看成两个部分的拼接A 前 n - k 个元素这些元素最终要往后移B 后 k 个元素这些元素最终要跑到前面原数组是A B目标结果应该是B A。现在执行三步反转第一步反转整个数组A B。反转后数组变为reverse(B) reverse(A)。这里 reverse(A) 表示 A 反转后的结果。第二步反转前 k 个元素也就是reverse(B)这个区间。反转一次后得到reverse(reverse(B)) B。此时数组变成B reverse(A)。第三步反转后 n - k 个元素也就是reverse(A)这个区间。反转后得到reverse(reverse(A)) A。最终数组变成B A。整个过程你看下来核心就是利用了“反转的逆操作还是反转”这个性质。把A B先整体颠个倒再分别把两个子段颠倒回来就完成了 A 和 B 的位置交换。这就是三步反转法“颠三倒四”却结果正确的原因。2.3 边界情况的数学梳理边界情况用公式推一下也很清楚当k 0时B 是空段三个反转分别作用于空区间等于什么都没做。数组保持不变符合预期。当k n时等价于k % n 0同理数组保持不变。比如 7 位数组轮转 7 位转了一圈回到原点。当k恰好是n / 2时A 和 B 长度相同三步反转相当于先把整个数组倒过来再把两半各自倒回来逻辑依然成立。当n 1时任何 k 取余后都是 0反转区间长度为 1没有实际效果。这里就引出了代码里必做的一步先执行k k % n。取余之后k 的取值范围变成[0, n-1]所有边界情况都被统一处理了。如果你不取余当 k 大于 n 时你反转的区间索引可能越界或者结果完全错误。3. 实操实现从伪代码到多语言落地3.1 反转函数的正确写法三步反转法的地基是反转函数必须写得又快又准。最简单的写法是双指针从两端向中间靠拢交换指针指向的元素def reverse(nums, left, right): while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1注意这里right是闭区间端点。如果你用的是半开区间约定也就是right不包含那最后一步right - 1的位置要格外小心。我的习惯是全程用闭区间左闭右闭这样三个反转的区间参数一眼就能对清楚。还有一点特别容易忽略反转函数的区间参数必须是合法的。如果传入的left right说明区间为空或者只有一个元素循环不执行直接返回。这个特性恰好帮我们处理了 k 取余后为 0 的情况。3.2 轮转主流程与 k 的预处理有了反转函数主流程就是三行调用外加一行取余预处理def rotate(nums, k): n len(nums) k % n reverse(nums, 0, n - 1) reverse(nums, 0, k - 1) reverse(nums, k, n - 1)你注意看这三行反转的区间第一行整个数组0 到 n-1第二行前 k 个元素0 到 k-1第三行剩余元素k 到 n-1三个区间无重叠、无空隙加起来正好是整个数组。这个记忆方式比死记硬背更可靠任何时候忘了怎么调你只要从“区间三段拼合成整个数组”这个角度想一想就记起来了。这里有个细节值得展开k % n应该在反转之前做而且必须基于 n 取余。如果 n 是 0也就是空数组取余运算会报除零错误。所以更严谨的写法是在函数开头判断if n 0 or k 0: return。LeetCode 的测试用例通常不会给空数组让你踩这个坑但自己写工程代码时要注意。3.3 各语言完整代码与差异点Python 版本注意不能用nums nums[-k:] nums[:-k]这种写法因为这是生成新列表再重新绑定变量名原数组没被修改。必须用上面那种切片式交换元素的方式或者通过索引逐一赋值def rotate(nums, k): n len(nums) if n 0 or k % n 0: return k % n def reverse(l, r): while l r: nums[l], nums[r] nums[r], nums[l] l 1 r - 1 reverse(0, n - 1) reverse(0, k - 1) reverse(k, n - 1)Java 版本注意 Java 没有 Python 那种优雅的解构赋值交换要用临时变量class Solution { public void rotate(int[] nums, int k) { int n nums.length; if (n 0 || k % n 0) return; 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--; } } }Go 版本跟 C/C 系列的写法非常接近func rotate(nums []int, k int) { n : len(nums) if n 0 || k % n 0 { return } k % n reverse(nums, 0, n-1) reverse(nums, 0, k-1) reverse(nums, k, n-1) } func reverse(nums []int, left, right int) { for left right { nums[left], nums[right] nums[right], nums[left] left right-- } }C 版本如果你不想手写循环可以用标准库的std::reverseclass Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); if (n 0 || k % n 0) return; k % n; reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() k); reverse(nums.begin() k, nums.end()); } };用std::reverse要注意迭代器区间是左闭右开所以reverse(nums.begin(), nums.begin() k)反转的是从开头到第 k-1 个元素刚好符合我们的预期。各语言对比下来核心逻辑完全一样差异只在语法层面。只要掌握了反转的语义和区间的分割方式任何语言你都能在五分钟内写出来。3.4 复杂度分析与性能实测时间复杂度上三次反转分别遍历 n、k、n-k 个元素总操作次数为n k (n-k) 2n所以是 O(n)。这里的常数系数 2 很有意义意味着无论 k 是多少操作总量都只跟 n 有关不会因为轮转距离大而变慢。空间复杂度上除了几个临时变量我们没有使用额外数组也没有递归调用栈所以是 O(1)。拿一个长度 100 万的数组实测随机选择 k 345678三步反转法的耗时通常在几十毫秒量级。相同场景下额外数组法虽然时间复杂度同样是 O(n)但由于多了一次数组分配和复制耗时会明显高一些。暴力法在这种数据规模下基本跑不动千万别在生产环境里用。另外说一个很多文章不会提的点反转循环里的元素交换在 CPU 层面是顺序访问缓存命中率很高。而额外数组法的写入和读取会跨两个数组进行缓存局部性稍差。所以在超大规模数组下三步反转法的真实性能优势比理论复杂度看起来更明显。4. 进阶细节环状替换与三步反转的取舍4.1 环状替换的运行逻辑环状替换是另一个 O(1) 空间的解法网上很多题解会提到。它不反转数组而是沿着“元素应该去的下一个位置”形成一条循环链。逻辑是这样的从索引 0 开始把nums[0]存到临时变量然后把nums[(0 k) % n]赋值给nums[0]再接着处理(0 k) % n这个位置把它的下一个目标位置的值搬过来……一直循环到回到起点。一个链条处理完后如果还有元素没处理就从下一个未被访问的位置开始继续。这个解法的代码比三步反转法长得多而且有一个隐含的数学问题需要访问多少条循环链答案是gcd(n, k)条。如果你不理解最大公约数很容易写错外层循环的次数。4.2 两种 O(1) 空间解法的适用场景面试时我会优先推荐三步反转法因为它的逻辑完全可预测不需要 gcd 这种数学知识打底也更容易跟面试官讲清楚。环状替换的优势在于它更接近“每个元素只移动一次”的直觉操作次数恰好是 n 次比三步反转法的 2n 次少了。实际运行时差距很小因为常数因子在算法层面可以忽略。但如果题目要求你原地轮转并且对稳定性有要求也就是说不能改变元素在各自分段内部的相对顺序那么三步反转法完全满足这个要求因为反转不会丢失相对顺序。环状替换同样保留相对顺序两种方案在这个维度上打成平手。我把一个真实面试场景的取舍讲给你听。有一次面试官看完我的三步反转实现后追问了一句“你能写一个每个元素只移动一次的版本吗”这就是在挖环状替换。我当时把两条循环链的原理讲清楚又补上了gcd(n, k)的推导面试官明显很满意。所以我的建议是主推三步反转但环状替换的原理也要准备万一被追问呢。4.3 衍生题型左旋、字符串反转、链表旋转三步反转法思路的根本价值在于它是一套“区间重排”的方法论换个包装就是新题目。左旋和右旋本质上是一对镜像问题。左旋 k 位可以视作“把前 k 个元素移到末尾”对应关系是反转整个数组反转前 n-k 个元素反转后 k 个元素。顺序刚好跟右旋相反。剑指 Offer 58 就有一道左旋字符串的题目用同样的三步反转就能解。还有旋转链表比如 LeetCode 61 题。链表的索引操作比数组麻烦但思路相通先遍历得到链表长度 n取余 k然后把链表连成环走到断开位置再拆开。它的本质就是把链表的尾部和头部接上然后从中间某个点断开跟数组的分块思想一模一样。再往广了说反转字符串里的单词顺序这道题也是先从整体反转整个字符串再逐个反转每个单词。这里的三步其实变成了“多步”但起点仍然是“整体反转后再局部反转”的策略。我把这类题整理成小表方便你按图索骥。题目类型操作核心与三步反转的关系右旋数组 k 位整反、反转前 k、反转剩余标准三步反转左旋数组/字符串 k 位整反、反转前 n-k、反转剩余调整区间即可反转句子中的单词整反字符串、逐个反单词多步局部反转旋转链表 k 次成环后定位断开点分块思想相同5. 常见问题与调试实录5.1 取模陷阱k 可能很大也可能是 0我见过最多的错误就是忘记取模。不取模时k 大于数组长度会导致反转区间的索引越界。例如数组长度 7k 10第三步的reverse(nums, k, n - 1)会变成reverse(nums, 10, 6)left 超过 right循环不执行结果数组是错的。更危险的是如果语言不检查数组边界你操作了非法区间可能污染其他内存。取模后为 0 的情况也要专门判断。如果 n 7k 14取模后 k 0此时三行反转依次是reverse(nums, 0, 6)、reverse(nums, 0, -1)、reverse(nums, 0, 6)。注意第二个调用传入了k-1 -1作为右端点。虽然双指针反转里left0 right-1不成立就不会执行逻辑没错但这种负索引的写法看着很别扭也可能在某些语言的严格检查下报错。所以我在代码习惯里都先加一行if k % n 0: return。5.2 反转函数参数越界问题反转函数的参数过界通常发生在边界处理不统一的时候。比如把k % n写在了反转之后这时候第一步反转用的是原始 k逻辑就全乱了。还有一种情况是 n 为 0 时空数组直接取余导致除零。虽然判题系统一般不会给空数组但你在本地测试或者写工具函数时这个异常会直接让程序崩溃。最好在一开始就做保护性判断。调试这类问题有个很实用的技巧先拿一个长度为 5 的数组逐一打印每次反转后的结果对比中间状态。例如nums [1,2,3,4,5]k 2。第一步反转后是[5,4,3,2,1]第二步反转前 2 个得到[4,5,3,2,1]第三步反转索引 2 到 4 得到[4,5,1,2,3]。如果中间任一步结果不对问题就出在对应区间的边界定义上。5.3 原地修改 vs 新建数组的陷阱Python 尤其容易踩这个坑。你写nums nums[-k:] nums[:-k]从运行结果看nums确实变了但 LeetCode 判题时检查的是原数组对象的内容不是局部变量nums的重新绑定。所以这种写法在功能上是错的。正确做法是原地修改也就是在同一个数组对象上通过索引逐一赋值。如果实在是想省事用 Python 的列表切片赋值技巧也可以nums[:] nums[-k:] nums[:-k]但这样本质上创建了新列表空间复杂度依然是 O(n)。想严格做到 O(1) 空间就只能用双指针反转法的原地交换。顺便提醒一句C 里如果你传参用的是值传递而非引用传递vectorint nums而不是vectorint nums那你在函数里怎么反转都不影响外部数组。这也是老生常谈却总有人忽略的坑。5.4 面试中的表述技巧面试时讲解三步反转法我推荐一个“三步讲法”第一步先讲清楚目标我们要把数组从A B变成B A其中 A 是前 n-k 个元素B 是后 k 个元素。第二步点出关键性质反转两次等于原样。所以我们可以先把整体反转把 A 和 B 的位置颠倒再把它们各自反转回来。第三步主动补充边界k 先取余为 0 直接返回保证反转区间合法且不用处理负索引。这个过程控制在两分钟内面试官一听就明白你不仅会写代码还理解原理。而且你用 A、B 分块的语言描述问题会比纯念代码更有说服力。我个人在实际面试和带新人的过程中发现很多人卡住的点不是反转函数本身而是“为什么反转三次能行”这个心理坎。一旦你把数组当成 A、B 两块来处理整个逻辑就通了。这也是为什么我觉得这篇文章最重要的不是代码而是 2.2 节那段数学推导。你把它看懂了三行反转闭着眼都能写对。最后分享一个我自己的调试小习惯所有数组算法题我都会用[1,2,3,4,5]加一个小 k 值先跑一遍再换一个k大于数组长度的用例跑一遍最后跑一次k 0的用例。三组测试覆盖了常规、取模、边界三种情况基本能过滤掉 90% 的隐患。这个方法不花时间但对提升代码的鲁棒性帮助很大你下次做题也可以试试。