企业官网建设流程全解析

布置的习题里有这么一道——习题2.2 数组循环左移。题干本身很短：把存放在一维数组 R 中的序列循环左移 p 个位置，也就是把 (X0, X1, ..., Xn-1) 变成 (Xp, Xp+1, ..., Xn-1, X0, X1, ..., Xp-1)，并且特别强调"时间和空间两方面都尽可能高效"。我第一次拿到这道题的时候，内心是很不以为然的：数组左移？把元素往前挪不就行了，存个临时变量十分钟就能写完。可真动手去设计、去分析复杂度、去处理各种边界条件之后，才发现这道题把数据结构课本里好几块硬知识点全串起来了。它同时关联到复杂度分析、原地算法设计和反转思想，后两者几乎是算法面试手撕代码的常客。所以这篇文章适合三类人：刚开始学数据结构、想把这题彻底弄懂的学生；准备笔试面试、想把这个经典原型吃透的求职者；以及工作中偶尔要处理数组旋转操作、想快速捡起通用思路的人。我会从最直觉的暴力搬移讲起，逐步推到最优的三次反转法，再把区间边界、取模处理这些最容易翻车的细节一次性说清楚。

1. 先把题读懂：循环左移和你想的那种"左移"不一样

1.1 题面细节："时间和空间尽可能高效"是什么意思

习题2.2 在不少教材里的完整表述是：设将 n 个整数存放到一维数组 R 中，设计一个在时间和空间两方面都尽可能高效的算法，将 R 中保存的序列循环左移 p 个位置，并给出算法的时间复杂度和空间复杂度分析。

这个题目看起来只有一句话，但考点密度相当高。它考的不是"你会不会写一个 for 循环"，而是你有没有把一个序列移动问题抽象成"下标经过某种映射后重新排列"的能力。注意"循环"两个字，它意味着数组的首尾是相接的——X0 被挤出去之后，不是丢掉，而是绕到数组尾部继续排队。这就和"左移一位丢掉队首"完全两回事。

"在时间和空间两方面都尽可能高效"这句话，我拆成两层意思。第一层，时间复杂度要尽量低，理想情况是 O(n)，因为每个元素至少要移动一次才能改变位置；第二层，空间复杂度也要尽量低，最好能做到原地操作，不额外开一个和原数组一样大的辅助数组。同时满足这两条，才是这道题的标准答案。很多初学者上来的解法满足了第一条却做不到第二条，或者反过来，这两种情况在作业批改和面试追问里都会被指出来。

1.2 用下标映射看懂移动的本质

如果你想把"移动"从"搬运"里抽出来，最可靠的方式是转成下标映射。

假设数组长度为 n，循环左移 p 位。对任意下标 i，它移动后的新位置是多少？

• 如果 i >= p，元素向左平移 p 位，新下标是 i - p；
• 如果 i < p，元素被顶出头部，绕到末尾，新下标是 i - p + n。

这两种情况可以统一写成：

new_index = (i - p + n) % n

这个式子看着简单，却是理解后面所有算法的基石。暴力法是围绕它一步步做，临时数组法是直接按它填位置，三次反转法则是在数学上等价地实现这组映射。我自己的经验是：拿到任何数组、字符串旋转类题目，先把下标映射式子写出来，再去看能用什么技巧简化搬运过程，思路会清晰很多。

这里还要多说一句：为什么是加 n 再取模，而不是直接写 i - p？因为在 i < p 时 i - p 是负数，很多编程语言里负数的取模结果和数学意义上的模并不一致，直接容易吃 hidden bug。统一写成 (i - p + n) % n，先把负偏移拉回正数范围，再取模，对所有 i 都成立。

1.3 一个常见误区：把循环左移当成简单前移

我第一次接触这类题时，写的代码是：先把第一个元素存到临时变量，把后面的元素一个个往前覆盖，最后把临时变量放到末尾。对"循环左移 1 位"来说这么写没错，但我很快就踩了一个坑：循环左移 p 位当然可以等于把"左移 1 位"这个动作重复 p 遍，可一旦 p 接近 n，代价立刻变得很难看，这个复杂度问题放到第 2 节详细算。

另一个更隐蔽的误区是把 p 直接当成"要挪的步数"，而忽略了 p 可能比 n 大。比如 n=5、p=7，循环左移 7 位和循环左移 2 位的结果完全一样。如果代码里没有先对 p 取模，反转时的区间直接越界，轻则结果错误，重则程序崩溃。这一点放到第 4 节专门讲，这里先记住结论：任何解法开头都必须先做 p %= n。

2. 两版保底解法：暴力搬移和临时数组，代价分别在哪

2.1 解法一：把一个元素从头搬到尾，循环 p 遍

先看看起来最顺的思路。把"循环左移"拆成"队首元素跑到队尾"这一个动作，循环左移 p 位就是把这个动作做 p 遍。

具体操作：外层循环跑 p 次，每次记录 array[0]，然后从下标 1 到 n-1 依次把后一个元素覆盖到前一个位置，最后把记录的 array[0] 写到 array[n-1]。

以 [1, 2, 3, 4, 5]，p=2 为例：

第一遍：记录 1，把数组变成 [2, 3, 4, 5, 1]； 第二遍：记录 2，再把数组变成 [3, 4, 5, 1, 2]。

结果是对的。时间复杂度很容易算：外层跑 p 次，内层跑 n-1 次移动，一共约 p × n 次赋值，写成 O(p × n)。如果 p 取到和 n 同数量级，那就退化成 O(n²)，n 一上了十万，这个方案基本跑不动。

空间复杂度倒是漂亮，只用了 1 个临时变量，严格 O(1)。我在实测里感受很明显：p 小的时候这种解法完全够用，代码还短；但只要你把 p 提上来，几万个元素乘以几万次移动，肉眼可见地卡顿。所以它只能作为"想一想为什么不行"的教材案例，不应作为最终提交的答案。

2.2 解法二：用额外空间直接把元素"投递"到新位置

第二种思路很直接：既然要整体移动，那就先算出每个元素的新位置，再开一个一样大小的数组，把元素直接写到新位置上去。

代码大概是：新建一个数组 temp，遍历原数组的每个下标 i，按 (i - p + n) % n 算出新下标，填入 temp；遍历完再把 temp 整体拷回原数组。

仍以 [1, 2, 3, 4, 5]，p=2 为例：temp 的下标 0 放原下标 2 的值 3，下标 1 放 4，下标 2 放 5，下标 3 放原下标 0 的值 1，下标 4 放原下标 1 的值 2，最终 temp = [3, 4, 5, 1, 2]，拷回原数组即可。

时间复杂度 O(n)，只遍历了两遍数组，比暴力法好一个量级，这是它的优点。但空间复杂度变成 O(n)，它需要额外一块和原数组一样大的空间。题目强调"时间空间两方面都尽可能高效"，所以这不是最优答案。

这里有一个小优化版本：临时数组只保存被挤出去的 p 个元素。先把原数组前 p 个元素拷到 temp，再把后面 n-p 个元素依次前移，最后把 temp 里的元素拼到尾部。这样空间复杂度降到 O(p)，p 不大时比 O(n) 好很多；但如果 p 接近 n，依然接近 O(n)。从面试角度看，能讲出"只保存被挤走部分"这个版本，说明对空间开销有概念，比一上来就开整个辅助数组的版本要加分。

2.3 四类方案的复杂度对照

把两种保底解法连同后面要讲的最优解放在一张表里，方便对比：

这张表建议直接背下来，它把"时间、空间、代码可读性"三者之间的取舍说清楚了。教科书为什么看重反转法，不是因为其他解法"错"，而是因为只有它做到了时间复杂度最优的同时完全不占额外空间。

3. 三次反转法：最优解的操作过程与正确性推导

3.1 三步反转的操作与手写示例

反转法的操作非常简短：对数组分三段反转，最后整体反转。

假设数组长度为 n，循环左移 p 位（已经做过 p %= n）：

1. 反转区间 [0, p-1]，也就是前 p 个元素；
2. 反转区间 [p, n-1]，也就是剩余部分；
3. 反转整个数组 [0, n-1]。

以 [1, 2, 3, 4, 5]，p=2 为例：

第一步，反转前 2 个元素得到 [2, 1, 3, 4, 5]； 第二步，反转后 3 个元素得到 [2, 1, 5, 4, 3]； 第三步，整体反转得到 [3, 4, 5, 1, 2]。

结果和预期完全一致。

这里有个细节值得注意：第一步和第二步的顺序可以交换。因为前 p 个元素和后 n-p 个元素是两个互相独立的区间，先反转哪一段都不影响另一段。真正的关键是第三步整体反转，它完成了一次"段落互换"。

3.2 为什么反转三次就能完成左移：用下标推导

我见过不少同学能照着写代码，但被问"为什么反转三次就能成功"时答不上来。这里用最直白的方式推导一遍。

先想一个简化版：数组由两段组成，A 段在前（p 个元素），B 段在后（n-p 个元素）。循环左移的本质就是让最终顺序变成 B + A。问题变成了：如何原地把 AB 交换成 BA？

直接"一段一段搬"做不到，因为 A 和 B 的长度通常不相等。反转法的巧妙在于利用了"区间连续反转两次会恢复原样"这一性质。前两次反转让 A 和 B 内部各自颠倒，第三次整体反转时，整个数组被倒过来，A 内的顺序被第二次倒回去，B 内的顺序也被第二次倒回去，但两段作为整体却完成了位置互换。

用刚才的例子验证得更精确。元素 1 原来在 A 段第 0 位，第一次反转后，它跑到 A 段的最右边；第三步整体反转后，它从"靠前的位置"被移到"靠后对应的位置"，正好落在数组尾部。而 B 段的第一个元素 3，在第二步反转后跑到了整个数组的末尾；第三步整体反转后，它又被送到整个数组的最前面。两段的位置彻底换了，段内顺序经过"两次反转抵消"后保持原样。

用数学式子写就是：设元素原始下标为 i，如果 i < p，最终位置为 n-p+i；如果 i ≥ p，最终位置为 i-p。这正是循环左移 p 位对下标的要求，和第 1 节那个映射公式完全一致。

3.3 复杂度分析：为什么它是"两全其美"

反转法的每次反转都是对一段区间做左右对称交换，每个元素在每次反转中恰好被交换一次。三段反转合计，每个元素最多参与三次交换，总赋值次数大约是 3 × n/2 次，属于常数因子很小的 O(n)。

空间上，所有操作都在原数组内部完成，只用了交换时的 1 个临时变量，严格 O(1)。

这就是"两全其美"的含义：时间达到下限量级，空间也达到下限量级，两者不互相让步。相比之下，临时数组解法时间虽然是 O(n)，空间却是 O(n)，相当于用一块额外空间偷懒；暴力解法空间 O(1)，时间却退化成 O(p × n)。只有反转法同时保住了两者的最优级别。

我还想提一个点：反转法的常数因子虽然小，但"三次反转、每次都交换一半元素"意味着顺序访问内存，这对 CPU 缓存是友好的，n 很大时也有实际意义。处理海量数组的区间翻转，这种写法往往比频繁随机访问临时数组表现更好。

4. 代码落地的关键细节：k值、空数组和反转边界

4.1 取模是任何实现的第一步

这是整道题里最容易被扣分的地方。循环左移 p 位，p 并没有限定必须小于 n。p=7、n=5 时，左移 7 位等于左移 2 位，因为每移动 n 位数组就恢复原样。因此所有实现的第一步都应该是：

p = p % n;

如果 p 此时为 0，说明不需要移动，直接返回。这个取模动作必须在任何区间计算之前完成，否则后续的 p 和 n-p 一旦越界，反转函数里的 left 和 right 就是错的。

如果是更通用的旋转工具函数，还应该考虑 p 传入负数的情况。有些语言里 p 是用户输入，可能出现负数。负的 p 可以理解成"反向移动"，安全的写法是：

p = (p % n + n) % n;

先把 p 压到 (-n, n) 范围，再补一次加法和取模，把负数修正到 [0, n-1]。Java 的 % 运算符对负数结果的符号跟随被除数，这一点务必注意。

4.2 边界条件的防守性写法

拿到数组先检查空与单元素：

if (n == 0 || n == 1 || p == 0) return;

n=0 和 n=1 时任何移动都没有意义，直接返回可以避免取模时除以零。C 语言里 n=0 时直接 p % n 会崩溃，尤其致命。我在写测试用例时一定会覆盖这几组：空数组、单元素、p=0、p=n、p>n、p 是 n 的整数倍。把这些跑通，这道题的正确性才有底。

还要注意"取模之后 p==0"也是一种边界：比如 n=5、p=10，取模后为 0，直接返回是对的；但如果代码里反转部分的区间写成 [0, p-1]=[0, -1]，就会出现空区间，虽然看起来无害，但依赖语言具体实现，最好提前用条件判断把它挡掉。

4.3 C、Java、Python 三种实现示例

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 leftRotate(int arr[], int n, int p) { if (n == 0 || n == 1 || p == 0) return; p = p % n; reverse(arr, 0, p - 1); reverse(arr, p, n - 1); reverse(arr, 0, n - 1); }

Java 版本几乎一样，注意数组是引用类型，方法内修改会直接作用于原数组：

static void reverse(int[] arr, int left, int right) { while (left < right) { int tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; left++; right--; } } static void leftRotate(int[] arr, int p) { int n = arr.length; if (n == 0 || n == 1 || p == 0) return; p = p % n; reverse(arr, 0, p - 1); reverse(arr, p, n - 1); reverse(arr, 0, n - 1); }

Python 用切片可以写得很紧凑：

def left_rotate(arr, p): n = len(arr) if n == 0 or n == 1 or p == 0: return p = p % n arr[:p] = arr[:p][::-1] arr[p:] = arr[p:][::-1] arr[:] = arr[::-1]

Python 里arr[:p][::-1]会创建临时切片，但切片长度只有 p，整体仍是原地修改原数组。如果在白板题里追求一行写完，也可以写arr[:] = (arr * 2)[p:p+n]，这属于"trick"写法，面试时能提一嘴作为额外方案，但不要作为主答案，因为可读性差。

4.4 反转范围选错：最典型的一类 bug

反转法代码不长，出 bug 的高发区全在区间边界。最常见的错误是把左移写成了右移的区间，或者端点差一位。

我归纳了一份自查表，写完后逐条核对：

这些错误大多数靠一两个手写例子就能暴露。我的习惯是：拿到代码后用 n=5、p=2 和 n=6、p=3 各手跑一遍，把每一步数组变化写在纸上，和预期结果比对。白板面试尤其适合这个方法，能一边写一边验证，比闷头写完再回头找错高效得多。

5. 从习题到面试：变形、延伸与我的几点体会

5.1 循环右移：和左移是一对镜像

循环右移和循环左移本质上是一对镜像操作。稍微推理一下：把数组循环左移 p 位，等价于循环右移 n-p 位；反过来，循环右移 q 位等价于循环左移 n-q 位。

面试里常见的题目会写成"给定数组，向右轮转 k 个位置"，其实就是循环右移。用反转法解决右移的步骤是：

1. 反转整个数组 [0, n-1]；
2. 反转前 k 个元素 [0, k-1]；
3. 反转后 n-k 个元素 [k, n-1]。

对比左移的做法会发现，顺序刚好相反：左移是先局部反转、后整体反转；右移是先整体反转、后局部反转。这两个方案放一起记容易混，我的记忆技巧是：先动手的那个反转决定了"最终头部元素的来源"——左移时头部来自原数组第 p 位，所以先反转前半段；右移时头部来自原数组末尾，所以先整体反转。

5.2 链表旋转与字符串翻转：同一个内核

这题还有两个很常见的变形场景。

第一个是链表的循环右移。数组用下标访问很方便，链表要靠"找断点"来切。思路是先把链表连成环，再根据数学映射找到新的头节点位置，然后断开环。链表的反转版做法也可以，先找新头节点，把后半段搬到前半段前面，也能原地完成，但边界处理比数组版本复杂。建议先把数组版本吃透，再去啃链表版本，因为核心还是同一个下标映射。

第二个是字符串翻转。语言层面的字符串反转往往有内置函数，但面试题喜欢抛"反转每个单词""按单词反转句子"这类问题，它们的内核同样是多次局部反转。比如"把一句话里的单词顺序倒过来，但单词内部字符顺序不变"，常见解法就是先整体反转，再对每个单词做局部反转，这和循环移位的三次反转思路同源。把习题 2.2 的反转思想理解透，等于给一大类反转类题目打底。

5.3 我在这道题上攒下的几条实操经验

这道题我看过不少初学者在它身上栽跟头，也自己反复写过，最后分享几个琢磨出来的体会。

第一，一定要亲手写一遍三种解法，而不是只抄标准答案。暴力法让你体会复杂度从哪来，临时数组让你体会空间从哪来，反转法让你体会数学技巧怎么把两者同时优化。只背反转法的三步操作，几个月后再遇到右移、旋转字符串，很可能还是不会变通。

第二，做题时把下标映射式子写在草稿纸最显眼的位置。(i - p + n) % n 这行公式，是我后来解决所有循环类问题的出发点。它看起来只是一个取模，实际把方向、边界、负数情况全部压缩了进去。

第三，练习时养成写测试用例的习惯。空数组、单元素、p 大于 n、p 为 0、p 为 n 的整数倍，全部跑一遍。很多面试者只在心里过一下，一上白板就错边界，这些细节恰恰是面试官最愿意追问的。

我自己曾经在右移题里因为"第一步该反转整体还是局部"纠结了很久，最后靠上面说的记忆技巧稳定住思路。这道题看起来简单，背后的设计思想却能延伸出一大片翻转类题目，希望这篇博客能把这题讲透，也帮你少走一点我走过的弯路。