数组循环左移算法全解析：从暴力破解到三次逆置法

这道题我在学生时代就遇到过，后来给备考的同学讲了很多遍，每次都有新体会。数组循环左移，说白了就是：给定一个长度为 n 的数组和一个整数 p，让数组里的元素整体向左移动 p 个位置，移出去的从左边“绕”回末尾。比如数组 [1, 2, 3, 4, 5, 6, 7, 8] 左移 3 位，结果是 [4, 5, 6, 7, 8, 1, 2, 3]。

看起来很简单，但真上手写代码时，会发现它像一面镜子，把你对数组遍历、边界处理、复杂度优化、甚至数学建模的功底照得清清楚楚。这篇文章把这道题的三种主流解法、边界条件、数学本质和衍生考点一次捋清楚，不管你是在准备期末考试、考研数据结构，还是刷算法面试题，都能用得上。

1. 循环左移到底在移什么：题目定义与三个容易被忽略的变种

1.1 一道习题的三层含义

很多教材里这道题的原型是：设将 n 个整数存放到一维数组 R 中，设计一个算法，将 R 中的序列循环左移 p（0 < p < n）个位置，并要求时间上尽可能高效。这里“循环”两个字是关键，它和普通平移的区别在于：普通平移会把数组顶出去的元素丢掉，而循环左移要求这些元素绕回数组另一端，数组的“总量”始终不变。

我在实际讲课中会把这道题拆成三个层次看待。第一层是基础层，要求能正确模拟“移出再绕回”的过程，这考察的是对数组下标和取模运算的理解；第二层是算法层，需要在时间复杂度和空间复杂度之间做权衡，从 O(n*p) 的暴力解，到 O(n) 时间、O(n) 空间的辅助数组解，再到 O(n) 时间、O(1) 空间的原地解，每一步都对应着不同的算法思维；第三层是数学层，如果能看出循环左移本质上是一个“置换”，那么很多看似花哨的原地算法（比如后面要说的分组移位法）就有了理论依据。

这道题之所以经典，正是因为它用一个小而完整的例子，串起了数组操作里最常见的考点：遍历、逆置、取模、复杂度分析、边界测试。一题吃透，等于把数组这块地基重新夯了一遍。

1.2 三种常见表述：数组左移、右移与字符串循环

做题时你会碰到这类题的多种“马甲”。最常见的就是数组循环左移和数组循环右移：左移 p 位相当于把前 p 个元素挪到末尾，右移 p 位相当于把后 p 个元素挪到开头。它们是互通的，右移 p 位等价于左移 n-p 位（在 p 小于 n 时），这一点后面会专门展开。

另一个高频变种是字符串的循环移位。字符串本质上就是字符数组，把 int 数组换成 char 数组，解题思路一模一样。有些题还会换个说法，叫“轮转数组”，比如某在线判题平台上的经典题“旋转数组”，要求把数组往右旋转 k 步，本质上就是这个习题的升级版。还有一类题要求判断“一个字符串能否通过若干次循环移位变成另一个字符串”，看起来绕，其实用的是另一个技巧：把源字符串拼接成两倍长度字符串，再检查目标字符串是否是其子串。

我在讲这些变种时经常跟同学强调一句话：不要背题，要背“需求”。这道所有变种背后的共同需求，就是“把数组切成两段，交换两段的位置，同时保持每一段内部的顺序不变”。抓住这个核心，后面所有解法都顺理成章。

2. 先说两个“能跑但未必好”的解法：暴力移位与辅助数组

2.1 暴力法：老老实实一次移一位

最容易想到的思路是一次移动一位，重复 p 次。每次移动时，先把第一个元素暂存起来，然后把后面的元素依次往前挪一格，最后把暂存的元素放到末尾。写成代码是这样：

c复制void leftRotateByOne(int arr[], int n) {
    int tmp = arr[0];
    for (int i = 1; i < n; i++) {
        arr[i - 1] = arr[i];
    }
    arr[n - 1] = tmp;
}

void leftRotate(int arr[], int n, int p) {
    for (int i = 0; i < p; i++) {
        leftRotateByOne(arr, n);
    }
}

这段代码逻辑是完全正确的，但性能就不好说了。假设 n 是 10 万，p 是 5 万，那么要移动 5 万轮，每轮要搬 10 万个元素，总操作量是 50 亿级别，这在笔试或面试里一旦数据量上来，基本等于超时。它的时间复杂度是 O(n*p)，空间复杂度是 O(1)。

不过我也要说句公道话，暴力法并不是一无是处。当 p 很小、n 也很小时，它是最直接、最不容易出错的答案。面试场景里，如果你能先快速给出暴力解，再说“但我们可以优化”，这本身就是一种良好的答题节奏。就怕你一上来就写花哨解法，边界条件还处理不对，反而暴露基本功不扎实。

2.2 辅助数组法：用空间换时间的标准答案

既然暴力法慢在“反复挪动”，那就干脆一次性算好每个元素的目标位置。观察一下规律就能发现：左移 p 位之后，新数组下标 j 上的元素，来自原数组下标 (j + p) % n。反过来，原数组下标 i 的元素，最终会落在新数组下标 (i - p + n) % n 的位置。用取模运算把所有“越界”的情况都统一处理掉。

基于这个映射，可以开一个同样大小的临时数组，一趟遍历完成搬运：

c复制void leftRotateWithAux(int arr[], int n, int p) {
    int aux[n];
    for (int i = 0; i < n; i++) {
        aux[(i - p + n) % n] = arr[i];
    }
    for (int i = 0; i < n; i++) {
        arr[i] = aux[i];
    }
}

这段代码的核心是那一行取模下标，它就是整个“循环”二字的数学表达。时间复杂度是 O(n)，空间复杂度是 O(n)。它最大的优点是直观、不易错，笔试时如果题目没有明确要求原地操作，写这个解法是稳赚不赔的。

我见过一些同学在这个解法里把下标公式记反了，写成了 (i + p) % n。其实验证一下就好：n=8、p=3 时，原数组下标 0 的元素 1，左移 3 位后应该到下标 5，而 (0 - 3 + 8) % 8 正好等于 5；如果用 (i + p) % n，下标 0 会算到 3，那就彻底错了。所以拿到这种题，先在草稿纸上手动推一个 8 元素、移 3 位的例子，很多错误都能提前规避。

2.3 两者的短板在哪里

暴力法和辅助数组法刚好站在两个极端：一个省空间但费时间，一个省时间但费空间。在一些内存受限的场景里，额外开一个等长数组是不可接受的。你想象一下，如果这个数组存放的是几十万条传感器采样数据，系统剩余内存本来就不多，再复制一份完整副本，风险不小。

更重要的是，算法面试里经常会有这样的追问：“能不能在 O(n) 时间内完成，并且不使用额外空间？”如果你只会上面两种解法，到这里就卡住了。所以第三部分要讲的原地逆置法，才是这道题真正的主角。

3. 三次逆置法：为什么 O(n) 时间和 O(1) 空间能同时满足

3.1 三步操作与一个实例

三次逆置法的思路极其简洁，只需要对数组做三次“逆置”操作。所谓逆置，就是把数组某一段的前后顺序完全颠倒。假设要左移 p 位，那么操作顺序是：

1. 逆置数组的前 p 个元素，也就是下标 [0, p-1]；
2. 逆置数组的剩余部分，也就是下标 [p, n-1]；
3. 最后逆置整个数组，也就是下标 [0, n-1]。

用一个例子推演就非常清楚了。还是数组 [1, 2, 3, 4, 5, 6, 7, 8]，左移 3 位：

最终结果和题目要求完全一致。每次逆置的代价是 O(段长)，三次逆置加在一起，操作量大概是 n 级别的常数倍，时间复杂度 O(n)，空间复杂度 O(1)。这个解法在理论和实践上都很漂亮，是这类题最推荐的标准答案。

3.2 为什么三次逆置能做到“换段”：一个翻牌类比

很多同学第一次看到这个解法时会有个疑惑：逆置三次，怎么就恰好把两段互换、并且段内顺序不变了？我第一次看到时也觉得像是魔术。其实背后道理可以用一个翻牌类比讲明白。

假设你把两叠牌分别放在左右手，牌面顺序都是正面朝上。第一步，把左手那叠牌整体倒过来；第二步，把右手那叠牌整体倒过来；第三步，把左右手合在一起的那一大叠牌整体倒过来。你会发现一个神奇的结果：原来左手的牌跑到右边去了，原来右手的牌跑到左边去了，而且两叠牌内部各自的顺序都恢复了最初的正向排列。

用符号来表达就是：对任意两段序列 A 和 B，先逆置 A 得到 reverse(A)，再逆置 B 得到 reverse(B)，最后逆置整体，得到的就是 B 和 A 的顺序，其中 B 和 A 内部又分别被“逆置了两次”，相当于没有逆置。也就是说 reverse(reverse(A)) = A，两次逆置互相抵消。这个性质是理解整个算法的钥匙。

这里我想多强调一句：逆置操作的“两次抵消”思想，在整个算法里反复出现。面试官问你“为什么这样能行”时，你如果能从“两段各自先逆置、再一次整体逆置让两段换位、又让段内顺序恢复”这个角度解释，会比他预期的“我会背这个方法”高级很多。

3.3 参考实现：reverse 函数怎么写才不容易错

三次逆置法的实现核心是逆置函数。我这里给一个左闭右闭区间的版本，也就是说调用时传入的 left 和 right 都是有效下标，两个端点都会被逆置：

c复制void reverse(int arr[], int left, int right) {
    while (left < right) {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        left++;
        right--;
    }
}

void leftRotateByReverse(int arr[], int n, int p) {
    if (n <= 1 || p % n == 0) {
        return;
    }
    p = p % n;
    reverse(arr, 0, p - 1);
    reverse(arr, p, n - 1);
    reverse(arr, 0, n - 1);
}

这个实现里我提前做了一件事：p = p % n。为什么需要取模？因为左移 n 位之后数组会回到原样，左移 p 位和左移 p % n 位的效果完全相同。不取模的话，如果 p 大于 n，reverse 的区间 [0, p-1] 就可能越过数组边界，这是非常隐蔽的崩溃点。

这里最容易出错的坑是区间约定不一致。比如你用的 reverse 内部是左闭右开（right 是不参与逆置的终点），那么调用时就应该写 reverse(arr, 0, p) 而不是 reverse(arr, 0, p-1)。两种约定都行，但一定要通篇统一。我的建议是在写 reverse 之前先写一行注释，标明“区间左闭右闭”，这样后面调用时就不会搞混。

4. p大于n、数组为空、区间写错：边界条件与实测验证

4.1 必须测试的几类边界输入

一道看似简单的数组题，能不能拿满分，很多时候看边界条件处理。我梳理了一份自测清单，建议你拿到这类题时逐个过一遍，尤其是面试前用来练手非常有效：

我在批改同学作业时发现，大多数人第一次写这道题都不会考虑 p > n 的情况。在教材原题里，条件写的是 0 < p < n，所以很多实现直接假定 p 一定小于 n。但实际工程或笔试题里，p 往往是任意整数，这时候就必须取模。你想想看，如果一段代码在 p 等于 n 的整数倍时直接越界崩溃，这种代码放进生产环境就是事故。

4.2 我踩过的两个典型错误

我自己最早实现这段代码时，踩过两个至今印象深刻的坑。第一个就是前面说的忘记对 p 取模。当时我用一个 n=8 的数组测试，p 传了 10，不取模直接用暴力法，结果功能看起来是对的——因为移动 10 位等价于移动 2 位，数组确实“碰巧”变成了正确结果。但性能坑了，多做了好几轮无用功，而且在大数据量下直接超时。后来我才意识到，功能正确不代表性能正确，取模这一步必须写在最前面。

第二个坑是 reverse 的边界写错。我某个版本用的是左闭右开区间，但在调用时按闭区间传参，导致每一段都少逆置了最后一个元素。这种 bug 特别阴险，因为数组小的时候，结果看起来只是某个位置不对劲，不容易想到是逆置长度错了。我后来总结出一个铁律：写任何区间操作前，先用 0、p、n 三个数字把每个区间的两个端点算一遍，确认它们落在有效范围内再动手。

4.3 随机对照测试：让两种方法互相验证

为了彻底消灭边界错误，我现在遇到这类题都会写一个简单的随机对照测试。思路是：用辅助数组法作为“参考答案”，用三次逆置法作为“被测实现”，随机生成大量 n、p 和数组内容，比较两种方法的结果是否完全一致。如果某个随机用例下结果不一致，说明被测代码里一定有 bug。

参考的测试框架可以写成这样：

python复制import random

def rotate_aux(arr, p):
    n = len(arr)
    if n == 0:
        return arr
    p %= n
    res = [0] * n
    for i in range(n):
        res[(i - p + n) % n] = arr[i]
    return res

def rotate_rev(arr, p):
    n = len(arr)
    if n == 0:
        return arr
    p %= n
    def reverse(a, l, r):
        while l < r:
            a[l], a[r] = a[r], a[l]
            l += 1
            r -= 1
    reverse(arr, 0, p - 1)
    reverse(arr, p, n - 1)
    reverse(arr, 0, n - 1)
    return arr

for _ in range(10000):
    n = random.randint(0, 20)
    p = random.randint(-50, 50)
    arr1 = [random.randint(0, 9) for _ in range(n)]
    arr2 = arr1[:]
    expected = rotate_aux(arr1, p)
    result = rotate_rev(arr2, p)
    if expected != result:
        print("mismatch", n, p, arr1, expected, result)
        break
else:
    print("all ok")

这个脚本里 p 的取值故意包含了负数和大于 n 的数，就是为了对边界情况进行压力测试。实际跑一轮，几千个随机用例覆盖下来，基本上能抓出九成以上的下标错误。这种“双实现互验”的方法，后来也成了我解其它算法题的固定套路。

5. 向上一步：循环移位的置换本质与分组原地算法

5.1 左移不是“平移”，而是沿环的置换

如果你只把循环左移理解成“把元素往前挪”，那三次逆置法已经够用了。但如果你想真正吃透这类题，我建议再从数学层面看一眼：循环左移本质上是一次置换。原数组下标 i 的元素，最终会跑到新下标 (i - p + n) % n 的位置；反过来，新下标 j 的元素来自原下标 (j + p) % n。这个映射把 n 个下标重新排列了一次。

这种置换有一个很有意思的结构：它由若干条互不相交的“环”组成。举个例子，n=8、p=3 时，因为 gcd(8,3)=1，整个数组是一个大环：0 号元素到 5 号位置，5 号元素到 2 号位置，2 号元素到 7 号位置……最后绕回 0 号位置，覆盖全部 8 个元素。而 n=8、p=2 时，gcd(8,2)=2，则会形成两个独立的环。

理解了这个结构，再看任何原地移位算法都会通透很多。为什么需要额外数组？因为你要把元素搬走，但搬走之后原位置又会被别的元素占用，如果不用额外空间记录，就得在环上做文章，让每个元素沿着环一次到位。

5.2 分组移位法（Juggling）的思路与实现

基于“环”的思想，可以设计出另一种原地算法：分组移位法，也叫杂耍算法。思路是先算出 g = gcd(n, p)，然后把数组分成 g 个独立的环组，对每个环组从起点开始，沿着环把元素依次往前搬，最终实现所有元素各就各位。

C 语言实现大致是这样的：

c复制int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

void leftRotateJuggle(int arr[], int n, int p) {
    if (n <= 1 || p % n == 0) {
        return;
    }
    p = p % n;
    int g = gcd(n, p);
    for (int start = 0; start < g; start++) {
        int tmp = arr[start];
        int i = start;
        while (1) {
            int j = (i + p) % n;
            if (j == start) {
                arr[i] = tmp;
                break;
            }
            arr[i] = arr[j];
            i = j;
        }
    }
}

这段代码初看不太好理解，核心在于内部那个 while 循环：它从一个环的起点 start 出发，每次都找“按左移规则应该占据当前位置 i 的那个元素”，也就是下标 j = (i + p) % n 处的元素，把它搬到 i 上，然后 i 跳到 j 继续。直到 j 回到 start，说明这个环转了一圈，把最初暂存的 tmp 放到当前 i 的位置，环就闭合了。外层循环再处理下一个环。

复杂度上，这个算法同样是 O(n) 时间和 O(1) 空间。但老实讲，它的常数因子比三次逆置法要大，代码也更难读，工程上我并不推荐优先使用。我把它放在这里，更多是想展示一种思考路径：当你理解了循环移位的置换结构，你就能自己推导出更“硬核”的原地解法。这种能力在算法面试的深度追问阶段非常吃香。

5.3 右移与左移的关系：一个 reverse 的变体

聊完了左移，来说说它的孪生兄弟右移。前面提到过，右移 p 位等价于左移 n-p 位，所以你可以直接用左移的解法，传入 n-p。但更常见的做法是用三次逆置的变体：先逆置整个数组，再逆置前 p 个元素，最后逆置剩余部分。

还是用 n=8、p=3 的例子验证一下。初始数组 [1, 2, 3, 4, 5, 6, 7, 8]，整体逆置得到 [8, 7, 6, 5, 4, 3, 2, 1]，逆置前 3 个得到 [6, 7, 8, 5, 4, 3, 2, 1]，再逆置后 5 个得到 [6, 7, 8, 1, 2, 3, 4, 5]。这就是右移 3 位的正确结果。

很多同学会记口诀：“左移先分段再整体，右移先整体再分段。”我的建议是，这个口诀可以辅助记忆，但更重要的是理解原理：不管左移还是右移，核心需求都是“交换两段的位置，保持段内顺序”，三次逆置只是实现这个交换的手段。一旦你从原理层面看懂了，不管题目怎么换方向，你都能现场推导，而不是靠背顺序。

6. 从这道习题长出来的面试题：右移、轮转与二分查找

6.1 从数组左移长出来的三个高频考点

这道习题在算法面试里的“后代”非常多。第一个高频考点是轮转数组，要求把数组右移 k 位，并且明确提出“尽量使用 O(1) 空间”。这个题的标准答案就是三次逆置，也就是刚才右移的变体。很多候选人在面试时能写出暴力法或辅助数组法，但只有真正理解“交换两段”思路的人，才能在追问下写出原地解法。

第二个考点是在旋转后的有序数组里做二分查找。这类题的背景是：一个原本升序的数组，在某处旋转了一下，比如 [1,2,3,4,5,6,7,8] 转成 [6,7,8,1,2,3,4,5]，要求以 O(log n) 的时间复杂度找到某个目标值，或者找到最小值。这里的关键观察是：每次二分，左半段和右半段中至少有一段是有序的，可以据此缩小搜索范围。这道题和循环左移是同一棵知识树上的果子，因为只有你熟悉旋转数组的结构，才能快速抓住“中点劈下去，必有一侧有序”这个性质。

第三个考点是字符串循环移位包含性问题：给定两个字符串，判断其中一个能否通过若干次循环移位变成另一个。最优做法不是真的去模拟移位，而是把源字符串拼接成两份，再检查目标字符串是否是这个拼接串的子串。这个技巧利用的正是“循环移位相当于在环形排列上滑动窗口”的直觉，和循环左移的下标取模思想一脉相承。

6.2 工程世界里的循环移位：环形缓冲与队列

别以为数组循环左移只是考试题，工程里的循环移位无处不在。最典型的是循环队列。实现循环队列时，读指针和写指针常常用 (tail + 1) % capacity 这样的方式推进，当指针走到数组末尾时自动绕回开头，这就是一个“一步循环移位”的嵌入式使用。再比如音频采集里的环形缓冲区、网络协议栈里收发数据包时经常用的环形队列，本质上都是“数组下标循环”这个名字的不同叫法。

还有一类工程场景是位运算里的循环移位，常出现在密码学、哈希函数和某些图像处理算法中。比如把一个 8 位二进制数循环左移 3 位，可以用 (x << 3) | (x >> (8 - 3)) 来实现，这里的逻辑和数组左移完全同构，只是元素从整数变成了比特位。

我在带项目时经常看到新人一遇到“下标越界”就想到扩容或者加分支判断，却很少有人想到取模运算和环形结构。如果你能在这道习题里把“下标取模”“环”这些概念用熟，到了工程里遇到缓冲区的读写回绕、轮询调度下标的推进，就能一眼看穿本质，少走很多弯路。

6.3 做题顺序与笔试面试中的表达技巧

最后说说我个人在笔试面试里更欣赏的答题节奏。拿到这道题，我建议按“暴力解 → 辅助数组解 → 原地逆置解”的顺序现场演进。先写暴力解，说明它的复杂度问题；再写辅助数组解，指出它用空间换了时间；最后写出三次逆置解，解释为什么逆置能交换两段且保持段内顺序。这个过程的每一步都展示了你的分析能力，而不是单纯背答案。

一个小技巧是，写 reverse 前先注释清楚区间约定，写完代码后主动补充几个边界测试用例，比如 p=0、p=n、p>n 的情况。这个动作虽然简短，却能在面试官心里留下“这个人写代码很稳”的印象。

这道题我前前后后讲了很多遍，几乎每次都有同学问：“为什么我想不到逆置？”我的回答是，这类题的突破口不是逆置本身，而是“两段交换”这个需求。数组上最廉价、最不容易出错的变换就是局部逆置，当你把“交换两段”翻译成“各自逆置再整体逆置”时，思路自然就通了。多练几道类似的题——比如字符串单词翻转、链表局部反转——这种翻译能力就会慢慢长在你身上。到那时候，再回头看这个习题，你会觉得它不再是背诵对象，而是一把能打开许多数组题的钥匙。