轮转数组

每转一步，后 n-1 个元素全体后移一位，k 次共做 n×k 次操作。k 接近 n 时直接退化成 O(n²)。得换思路。

笨办法演示 · 挪之前：末位 7 待移：朴素法：每次把末尾元素插入头部，其他 n-1 个元素全体右移一位。

笨办法演示 · 挪 1 次只转 1 格：挪 1 次只完成 1 格轮转，k=3 就要挪 3 次，每次移动 n 个元素，总代价 O(n·k)，k 接近 n 时退化成 O(n²)。必须换思路。

右转 k 步等于把后 k 个挪到前面。先整体反转，再分两段反转，三刀就还原了真正想要的顺序——O(n) 时间、O(1) 空间。

为什么有效 · 分清 A 段和 B 段：k=3，所以后 k=3 个元素组成 B 段（高亮），前 n-k=4 个是 A 段（暗色）。轮转的本质就是把 B 搬到 A 前面——但怎么原地搬？靠三次反转。

初始状态 · k%=n 先取模：第一件事：k 对 n 取模。k=10、n=7 时其实只转 3 步；不取模会白做功。

第一次反转 · 整体 [0, n-1]，l=0 r=6：第一次反转开始：l 从最左、r 从最右向中间靠拢，两两交换。

第一次反转 · 交换 1↔7：1 和 7 交换完毕，l 右移、r 左移，继续向中间夹。

第一次反转 · 交换 2↔6：2 和 6 交换。

第一次反转 · 交换 3↔5，完成整体反转：3 和 5 交换，l 和 r 相遇，整体反转完成：[7,6,5,4,3,2,1]。

为什么有效 · 整体反转后 A'、B' 都已换位：整体反转做了两件事：① A 和 B 的相对位置互换（B' 跑到前面了）；② A、B 各自内部顺序颠倒。接下来对 B' 单独反转还原 B，对 A' 单独反转还原 A，最终正是 [B|A] = 轮转结果。

为什么有效 · 对比图：各段倒序了，所以再各自反转：高亮=B'=[7,6,5](目标是5,6,7，倒序了);暗色=A'=[4,3,2,1](目标是1,2,3,4，也倒序了)。各自再反转一次就回正序，三刀结束。

第二次反转 · 前 k=3 个 [0, k-1]：第二次反转只动前 k=3 个。把 reverse(B')=[7,6,5] 变回 B=[5,6,7]。

第二次反转 · 指针对撞 swap nums[0] 与 nums[2]：l=0、r=2 对撞：高亮的 7 和 5 互换。中间的 6 不参与此次交换。交换后 l 和 r 都指向 1，循环结束。

第二次反转 · 交换完毕 [5,6,7,4,3,2,1]：前三个反转好了：5、6、7 回到正序，它们就是轮转后的前三个。

第三次反转 · 后 n-k=4 个 [k, n-1]：第三次反转只动后 n-k=4 个。把 reverse(A')=[4,3,2,1] 变回 A=[1,2,3,4]。

第三次反转 · 交换 4↔1：4 和 1 交换完毕，继续夹。

第三次反转 · 交换 3↔2，完成！：3 和 2 交换，后四个变成 [1,2,3,4]，最终结果 [5,6,7,1,2,3,4]。三次反转搞定！

把这句话记住：整体反转相当于把 A 和 B 的顺序颠倒同时把各自内部也颠倒，再各自修正一遍，就还原出 B+A。

边界三连：三个边界全靠第一行 k %= n 兜住。这行漏写，k=n 时会白转一圈、k=0 时下标可能越界。

雷区实演 · 忘了 k%=n 时 k=0 的情形：k=0 时三步的净效果是两次整体反转互相抵消，数组完全不变。k=n 若不取模，rev(0, k-1)=rev(0, n-1) 变成整体反转而非前段反转，结果全错。第一行 k%=n 是整个算法的安全阀。

面试追问：轮转数组的面试追问集中在「为什么有效」「空间对比」「取模必要性」三个点，提前想清楚。

三刀归位 · 回放全过程：三刀全部落完：[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]。

迁移阶梯：掌握三次反转后，字符串的循环移位（LC796 旋转字符串）、原地旋转矩阵（LC48）都能用「反转分段」思路迁移。进入数组专题继续刷。