189. 轮转数组

难度：🟡 Medium | 标签：数组、三次反转 | 状态：⬜ LeetCode 链接

思路

三次反转法：原地、O(1) 空间。

1. 反转整个数组
2. 反转前 k 个
3. 反转后 n-k 个

注意 k %= n，否则越界。

代码

class Solution {
public:
    void rotate(vector<int>& 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());
    }
};

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• k %= n 必加
• 三次反转的边界点是 begin() + k
• 也可用辅助数组 O(n) 空间，但本题考点是 O(1) 空间
• 环状替换法（gcd）也是 O(1)，但代码更难