开篇先聊聊一个问题给定一个数组[1,2,3,4,5,6,7]要求把数组整体右移 k 位得到[5,6,7,1,2,3,4]k3。这题看起来不难但真正会写的人一抓一大把有人直接新建一个数组硬拷贝有人写了嵌套循环挨个挪跑完一提交才发现时间爆炸。而三次旋转法也就是常说的三次反转法能在 O(n) 时间、O(1) 额外空间内解决思路干净代码短几乎是所有技术社区和面试场景里公认的标准方案。我打算从原理、代码、边界坑到变体应用把这套方法完整拆一遍尽量把每一步的“为什么”都说清楚让读者不仅能抄作业还能真正理解它。这题适用面很广面试算法刷题、笔试手撕代码、工程里做环形缓冲区的偏移处理都可以用到。如果你正在准备技术面试或者只是想把数组操作的基础打扎实三次旋转法都是绕不开的一块内容值得认真吃透。1. 先认清问题旋转数组到底在做什么1.1 从日常场景出发理解旋转数组旋转不是凭空想出来的抽象题它在工程里的映射非常直接。最常见的就是循环队列里元素整体偏移、轮播图列表的索引切换、分页数据在固定窗口内的偏移展示还有字符串加密里常见的字符位移。本质上数组旋转解决的都是同一件事在一个连续存储的序列里把尾巴上的一段元素搬到头部同时保持段内元素的相对顺序不变。举个例子一个团队按[A,B,C,D,E]顺序值班要求每周轮换一次那么第二周就要变成[E,A,B,C,D]。这种轮换如果每次都用临时数组做数据量小的时候感觉不到什么但一旦元素个数到了百万级别、轮换操作频繁触发效率差距立刻就会被放大。三次旋转法的价值就在这里它不需要额外开辟一块等长的内存也不需要逐个移动元素仅仅通过反转操作就完成了整体偏移这也是它在算法题解里高频出现的原因。需要注意这里的旋转方向有两种左旋和右旋。左旋是指把前 k 个元素移到末尾右旋是指把后 k 个元素移到开头。三次旋转法在两种方向上的实现逻辑完全对称核心套路一样只是区间切分的位置和顺序不同。我习惯先统一理解成“旋转 区间互换”后面就不会混淆了。1.2 暴力解法为什么不能直接用写代码之前先把暴力方案摆出来对比思路会清楚很多。最容易想到的两个方案第一种额外数组拷贝。新建一个同样大小的数组用取模运算(i k) % n计算每个元素的新位置然后写回。这个方案时间复杂度 O(n)已经很好了但空间复杂度是 O(n)。如果题目明确要求原地修改、只能使用常数额外空间这个方案直接出局。第二种逐位移动。每次把数组整体右移一位重复 k 次。这个方案空间复杂度是 O(1)但时间复杂度退化到 O(n * k)。当 n 和 k 都比较大的时候性能完全不可接受。比如 n100000k50000意味着五亿次移动实测能跑出肉眼可见的延迟。三次旋转法恰好卡在中间空间 O(1)时间 O(n)两个指标都最优。这也是它成为标准答案的根本原因。2. 三次旋转法核心原理与思维推导2.1 从数学规律到反转操作先抛出这个算法的核心结论要将数组右旋 k 位等价于按顺序执行三次数组反转。设数组长度为 n先把 k 对 n 取模得到有效偏移量k_mod k % n。然后反转整个数组反转前 k_mod 个元素反转后 n - k_mod 个元素。以[1,2,3,4,5,6,7]、右移 3 位为例手动走一遍全部反转[7,6,5,4,3,2,1]反转前 3 个[5,6,7,4,3,2,1]反转后 4 个[5,6,7,1,2,3,4]得到的结果和预期完全一致。左旋的情况正好相反先反转前 k 个再反转后 n-k 个最后整体反转。比如[1,2,3,4,5]左移 2 位反转前 2 个[2,1,3,4,5]反转后 3 个[2,1,5,4,3]全部反转[3,4,5,1,2]也很符合预期。这个模式很优雅但第一次接触的人都会问为什么偏要反转三次2.2 三次反转的排列学解释要理解原理得从数组分段的角度看。假设数组原本分成两段A 段前 n-k 个元素和 B 段后 k 个元素。原始顺序是[A | B]右旋后的目标顺序是[B | A]。三次反转做的事情本质上是通过三次反转把两段的位置互换同时保持段内顺序不变。反转操作有个非常重要的性质对任意序列执行两次反转等于还原。这个性质成立是因为反转是自身的逆操作。基于这个性质可以拆解三次反转的过程第一次反转整个数组。数学上整体反转等价于把 A 段和 B 段分别反转后互换位置即[A^r | B^r]。这里的A^r表示 A 反转后的结果。第二次反转前 k_mod 个元素。此时前 k_mod 个元素对应的是原来的 B 段已经被反转成B^r再反转一次就变回B。第三次反转剩余的 n - k_mod 个元素。这些对应原来的 A 段已经变成A^r再反转一次就变回A。整个过程用符号表达就是初始状态[A | B]整体反转[B^r | A^r]前段反转[B | A^r]后段反转[B | A]动作顺序的记忆方法很简单右旋就先整体反转再分开反转左旋就先分开反转再整体反转。一句话记法“右拳出击先整体再局部左拳防守先局部再整体。”实际做题的时候拿小数组快速走一遍就能确认方向。2.3 边界情况k 溢出与负值处理这里有个新手最容易踩的坑就是忘记对 k 取模。k 有可能大于 n比如[1,2,3]右移 5 位实际等价于右移5 % 3 2位。不取模直接进入反转流程计算反转区间时就会越界当场报错。更隐蔽的问题是 k 为负值。有些题目的接口允许 k 为负数表示反向旋转。处理方式很简单如果k 0把它换算成k k % n n或者直接k n - (-k % n)再走正常流程。比如 n7k-2实际等价于右移7 - 2 5位。还有一类边界是特殊值k0 时不执行任何操作n1 时无论 k 取什么数组都不变k 恰好等于 n 时旋转一圈又回到原样。这些在实现里都应该走快速分支直接 return省去不必要的计算。我个人的习惯是把取模和负值处理放在同一个函数入口处统一收敛保证内部逻辑只处理0 k n的干净状态后续所有区间计算都不用再考虑异常情况。3. 完整代码实现与实操细节3.1 Python 实现最短最容易理解的版本Python 的切片语法让三次旋转法写出来可以非常短。下面是完整的函数实现def rotate(nums, k): 原地右旋数组 nums k 位。 :param nums: List[int] :param k: int n len(nums) if n 1: return k k % n if k 0: return def reverse(start, end): # 左闭右闭区间 [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) # 第二次反转前 k 个 reverse(k, n - 1) # 第三次反转后 n-k 个这个实现最核心的辅助函数是reverse(start, end)我选择左闭右闭区间写法。变量start和end分别是当前要交换的首尾索引每次交换后向内收缩。注意end的初值是k - 1而不是k这个细节如果搞错翻转范围就会多一个元素或少一个元素。很多拿不到满分的答案问题就出在这种边界上。至于为什么用内层函数而非全局函数纯粹是为了把辅助逻辑封装在rotate内部避免外部误用也让这题的代码结构更紧凑。在键盘上几十秒就能写完一版特别适合笔试场景。3.2 C 实现性能敏感场景的标准写法C 版本和 Python 的逻辑完全一致区别在于可以使用标准库的std::reverse代码更精简而且标准库实现通常有不错的编译器优化#include vector #include algorithm void rotate(std::vectorint nums, int k) { int n nums.size(); if (n 1) return; k % n; if (k 0) return; std::reverse(nums.begin(), nums.end()); std::reverse(nums.begin(), nums.begin() k); std::reverse(nums.begin() k, nums.end()); }这版本有一个值得注意的地方std::reverse的区间是[first, last)左闭右开所以第二个反转的结束迭代器是nums.begin() k实际翻转的是下标0到k-1。第三个翻转从nums.begin() k开始到end()覆盖下标k到n-1。C 的迭代器区间设计在工程里很常见如果平时写 Java 的subList或者 Python 的切片对左闭右开的语义应该不陌生。但如果你以前写的是左闭右闭下标刚切换到迭代器时很容易把k错写成k-1这个点我在实际 code review 里见过不止一次。3.3 不同语言实现的关键注意点虽然三个语言思路完全一样但细节差异有时会直接决定成败。整理一个对比表方便读者对照检查语言反转区间语义常见错误解决建议Python切片a[::-1]左闭右开手写 reverse 时 end 边界算错用左闭右闭并统一测试几个小用例C迭代器[begin, end)第二个 reverse 结束位置写成begink-1画区间图确认JavaCollections.reverse仅支持 List对Arrays.asList以外的数组需手写写一个swap子函数复用补充一个 Java 范例因为 Java 是很多面试的主语言。基本类型数组没有现成的reverse接口手写反转循环几乎不可避免public void rotate(int[] nums, int k) { int n nums.length; if (n 1) return; k % n; if (k 0) return; 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 tmp nums[left]; nums[left] nums[right]; nums[right] tmp; left; right--; } }Java 这个版本的reverse用的也是左闭右闭和 Python 内层函数保持一致。面试时我会建议候选人在写完之后立刻用n6, k2这种小用例在脑子里或纸面上走一遍只需要一分钟就能避免绝大部分边界错误。4. 复杂度分析与在不同方案中的定位4.1 时间复杂度推导三次旋转法的时间复杂度很好算。每次反转本质上是一趟线性扫描交换区间长度/2次。三次反转的区间长度加起来正好是n的两倍第一次n/2次交换第二次k/2次第三次(n-k)/2次总计n次交换每次交换是常数时间操作所以整体时间复杂度为 O(n)。空间上额外变量只有start、end、tmp几个与输入规模无关空间复杂度 O(1)。为了更直观地感受为什么它比逐位移动快以 n100000、k50000 为例三种方案对比方案时间复杂度空间复杂度n100000, k50000 时的操作次数估算逐位移动O(n*k)O(1)约 50 亿次元素移动额外数组O(n)O(n)约 10 万次拷贝 10 万内存空间三次旋转O(n)O(1)约 5 万次交换这里的 5 万次交换就是纯交换 50 万次赋值远小于 50 亿。差距是四个数量级到真实运行环境里就是几毫秒和几十秒的差别。4.2 与环状替换法的对比三次旋转法不是唯一的 O(n)/O(1) 方案。另一种经典解法是环状替换法也叫原地 index 跳跃法。它的思路是从某个起始位置出发用tmp保存被挤掉的元素然后沿(i k) % n的路径跳转到下一个位置一路上将元素依次放置到正确位置直到回到起点再换下一个起点继续。这个方法也满足 O(n) 时间和 O(1) 空间但有个隐藏难点如果一个环走完但没有覆盖所有元素需要多个起点迭代而正确选择起点个数和判断环结束的时机并不直观容易写错死循环。对比之下三次旋转法的实现逻辑要简单得多每个反转都是确定性的区间操作不容易写错也容易写单元测试。在面试和工程中我都会优先选择三次旋转法。环状替换更适合作为进阶理解或者题目明确要求“每次移动一个元素次数尽量少”的特殊场景。4.3 面试中的常见追问与解题策略面试官如果问旋转数组大概率不会只满足于“你会背公式”。常见的追问有“如果 k 是负数怎么办”——答对 k 取模后转成正数偏移或者分类讨论左旋。“如果要求返回新数组而不是原地修改呢”——答那就直接用额外数组法反而更简单没必要原地反转。“如果输入不是数组而是链表呢”——答链表旋转的思路完全不同通常需要先求长度、再断链、再拼接不是简单的反转三段。“反转函数的实现里用到了交换这里会不会有整数溢出”——答交换的是数组元素的值不是索引加减后的大整数不会溢出但要小心索引计算时i1越界。准备面试时我建议按“暴力解法 → 三次旋转法 → 环状替换法”三步递进复习。先理解暴力解法为什么慢再理解三次旋转为什么快最后看环状替换作为补充这样一个知识树就完整了。只背一个答案不仅容易出破绽遇到变形题也容易懵。5. 常见问题与排查技巧实录5.1 区间边界算错的经典案例我自己在早期写这题时踩过的最深坑就是把第二次反转的结束位置写成k而不是k-1。想象一下 n5、k2 的情况右旋的正确目标应该是把最后两个元素挪到最前面。如果第二次反转的是[0,2]闭区间就会把第三个元素也卷进反转范围最后得到的结果整体错位。这种错误在纸面上走读时很容易忽略因为样例输出恰好也有点像“旋转过”只是元素顺序不对。排查技巧其实很简单手动选一个 n5k2 的小数组拿纸笔推演一遍把每次反转后的数组状态写下来对比期望值。任何一个区间参数错了状态都会在某一步显形。我现在的习惯是写代码前先写下三个反转的区间边界作为注释再动手实现这样能避免大部分笔误。5.2 原地修改与返回值不一致的困惑还有一个非常常见的坑尤其在 Python 里写了def rotate(nums, k)函数内部对nums做了原地修改但最后又return nums。这本身没问题但有些人在函数开头写了nums nums[-k:] nums[:-k]以为这样就是原地修改实际上这行代码把局部变量nums指向了一个新列表外部传入的数组根本没变。调用方一检查发现原数组还是原样然后 debug 半天。如果确实想做原地修改千万不要在函数内部重新赋值整个变量名你要么直接操作下标元素比如nums[i] ...要么在函数开头把新值铺回去。最稳妥的写法就是前面 3.1 节的双指针交换版本全部操作都是对元素赋值不会出现“改了但没完全改”的问题。5.3 反转函数自身的效率问题有读者会问手写反转循环和标准库reverse性能差距大吗实测下来C 标准库的std::reverse通常比手写循环好一些因为它可能被编译器优化成向量化的批量赋值尤其是元素类型是 POD普通旧数据时差距更明显。而 Python 手写while循环交换反而比切片反转要慢因为 Python 层级的循环开销大于底层 C 实现的切片操作但 Python 的切片会产生新列表占用额外内存。追求简洁可以用切片写追求严格的 O(1) 额外空间就用手写循环。工程实践中更建议用第一种写法也就是手写双指针原地交换通用性最强。6. 扩展应用与个人实操体会6.1 从数组到字符串同一个套路换个壳三次旋转法的应用不局限于整数数组。字符串旋转是一模一样的问题比如判断两个字符串是否互为旋转词这类面试题或者 KMP 算法里的循环位移处理本质上都是数组旋转的应用场景。举一个很直接的例子字符串abcde右移 2 位得到deabc。判断一个字符串s2是否是s1的旋转词常见解法是检查s2是否在s1 s1里这个方案的原理和三次旋转法其实是相通的s1 s1天然包含了所有旋转结果。如果让你不借助s1 s1的新增内存就可以用三次旋转法对s1进行位移后逐位比较。这类变体在面试里经常出现思路都是一根藤上的瓜。6.2 链表旋转的区别提醒链表旋转和数组旋转表面相似但解法路径完全不同。链表无法随机访问三个反转需要遍历找断点一般是先遍历求长度 n再把 k 取模然后移动指针到断点位置最后调整几个节点的 next 指向即可。这个操作时间也是 O(n)空间 O(1)但代码写起来和数组版本差别很大。我见过不少人面试时把数组的reverse函数硬套到链表上结果不是超时就是报错所以这里单独提醒一句不要惯性迁移先判断容器的访问模型。6.3 小技巧用取模简化可读性最后分享一个我自己觉得好用的小技巧。在最终实现里可以不用三次反转而是直接用取模重新排列适合不需要原地改的场景def rotate_new_array(nums, k): n len(nums) k % n return nums[-k:] nums[:-k]这行代码虽然简洁但它的空间复杂度是 O(n)只能在允许额外空间的时候用。如果面试官明确要求“原地”还是得回到三次反转。在平时写工程代码时如果数据规模可控、并没有严格要求 O(1) 内存我反而经常用这种切片写法因为可读性极高后维护的人一眼就懂。算法题和工程代码的目标并不总是一致懂得在不同约束下选不同实现才是真正的经验。我在实际写这道题的时候最大的体会就是三次旋转法看起来简单但真正吃透它需要把“为什么会这样”想明白。单纯的记忆不够因为你迟早会遇到 k 为负、k 大于 n、需要返回新数组等变体只有理解了区间互换的本质才能在任何一种变形里快速推断出正确的反转顺序。希望这篇拆解能帮你把这道题彻底拿下再遇到旋转数组的题目直接心里有底。