[!info] related notes

轮转数组

这道题目在面试和算法练习中非常经典，它表面上是考察对数组的移动操作，但核心考察的是开发者对时间和空间复杂度的权衡能力，以及对特定数组操作技巧的掌握。

具体来说，它主要考察以下几个维度：

1. 边界条件的处理（数学思维）

首先考察你是否能意识到 k 可能会大于数组长度 n。

如果是这样，轮转 n 次后数组会回到原样。因此，第一步必须是利用取模运算降低工作量：k = k % nums.length。如果不做这一步，遇到极端测试用例（比如数组长度为2，k为100000）就会超时或做无用功。

2. 从直觉到最优解的优化能力（进阶要求）

题目特别强调了“想出三种不同的方法”和“O(1) 空间的原地算法”。这正是面试官最喜欢的递进式提问：

• 基础解法（空间换时间）：使用额外数组
  • 考察点： 基础的下标映射逻辑。
  • 思路： 能够推导出原数组索引 i 的元素，轮转后会落到新数组的 (i + k) % n 的位置。这个方法时间复杂度 O(n)，空间复杂度 O(n)。
• 进阶解法（原地算法）：环状替换法
  • 考察点： 逻辑严密性和一点点数学（最大公约数）。
  • 思路： 把元素直接放到它最终的位置上，被占位置的元素再继续找它的下一个位置，像击鼓传花一样。难点在于处理“回到起点形成死循环”的情况，考察对变量状态的维护能力。空间复杂度降到了 O(1)。
• 最优/最巧妙解法（原地算法）：数组翻转法
  • 考察点： 对数组局部结构规律的洞察力。
  • 思路： 这是这道题最经典的解法，也是面试时最期望看到的解答。通过三次简单的翻转，就能实现元素的整体位移，代码极其简洁，且空间复杂度完美保持在 O(1)。

翻转法图解（极其巧妙）

以 nums = [1,2,3,4,5,6,7], k = 3 为例：

1. 整体翻转： [7, 6, 5, 4, 3, 2, 1]
2. 翻转前 k 个元素 (前3个)： [5, 6, 7, 4, 3, 2, 1]
3. 翻转剩余的 n-k 个元素 (后4个)： [5, 6, 7, 1, 2, 3, 4] (得到最终结果)

---

总结来说，这道题是一块很好的试金石，能看出你是只会用最直接的方法（额外数组），还是掌握了巧妙的算法思维（翻转法/环状替换）。

三次反转法

“三次翻转法”的实现非常优雅，它的核心思想是：通过局部倒序的组合，达到整体循环位移的效果。

为了实现原地（O(1) 空间复杂度）的翻转，我们需要自己写一个双指针的辅助函数，用来将数组中指定范围 [start, end] 内的元素进行首尾对调。

以下是具体的代码实现和拆解说明。为了方便你和之前的代码无缝衔接，我依然使用 TypeScript 编写：

核心代码实现

/**
 * Do not return anything, modify nums in-place instead.
 */
function rotate(nums: number[], k: number): void {
    const n = nums.length;
    
    // 1. 处理 k 大于数组长度的情况，这步非常关键
    k = k % n; 
    
    // 提前返回，如果数组只有一个元素或不需要轮转
    if (n < 2 || k === 0) return;

    // 辅助函数：使用双指针反转数组的局部区间 [start, end]
    const reverse = (arr: number[], start: number, end: number): void => {
        while (start < end) {
            // 交换首尾元素
            const temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            
            // 指针向中间靠拢
            start++;
            end--;
        }
    };

    // 第 1 次翻转：翻转整个数组
    reverse(nums, 0, n - 1);
    
    // 第 2 次翻转：翻转前 k 个元素
    reverse(nums, 0, k - 1);
    
    // 第 3 次翻转：翻转剩余的 n - k 个元素
    reverse(nums, k, n - 1);
};

---

为什么这样能行？（逻辑剖析）

假设我们有一个数组 [1, 2, 3, 4, 5, 6, 7]，我们要向右轮转 k = 3 个位置。

你可以把数组想象成两截拼在一起的：

• A段（不需要挪到前面的元素）：[1, 2, 3, 4]
• B段（需要挪到前面的元素）：[5, 6, 7]

我们的目标是变成 B + A，即 [5, 6, 7, 1, 2, 3, 4]。

1. 第一步 reverse(nums, 0, n - 1)： 将整个 A + B 翻转，变成了 B的倒序 + A的倒序。 结果：[7, 6, 5, 4, 3, 2, 1] 此时，原本在后面的元素虽然跑到前面来了，但是它们内部的顺序反了。
2. 第二步 reverse(nums, 0, k - 1)： 把前 k 个元素（也就是 B的倒序）再翻转一次，负负得正，变成 B的正序。 结果：[5, 6, 7, 4, 3, 2, 1] 此时，前 3 个元素已经完全符合最终要求了。
3. 第三步 reverse(nums, k, n - 1)： 把后面剩下的元素（也就是 A的倒序）再翻转一次，变成 A的正序。 结果：[5, 6, 7, 1, 2, 3, 4] 至此，大功告成！

复杂度评估

• 时间复杂度：O(n)。各个元素最多被访问和交换两次（一次在整体翻转，一次在局部翻转），所以总时间消耗与数组长度成正比。
• 空间复杂度：O(1)。我们只使用了几个额外的变量（temp, start, end, n, k），没有开辟新的数组，完全是在原数组上进行操作（in-place修改），完美符合进阶要求。