交换数组的两部分真的很简单吗？
一开始，写算法的时候总是想搞出各种骚操作，特别想设计出像红黑树这样酷似耍杂技的玄妙算法。但是见过的算法问题多了之后，越来越喜欢那些简洁易懂的算法。因为简单的，一般也很有效。
今天说一个看起来很简单的问题：交换数组的两部分。比如数组【1,2,3,4,5】，要将【1,2,3】和【4,5】交换，得到【4,5,1,2,3】。
这个操作真的和看起来一样简单吗？对于没有思考过这个问题的人，真的很难，不信你试试。但这个问题有很多开脑洞的思路，而且其中最简单的解法也是由最基本的操作组合成的。
先看一道类似的 LeetCode 题目：
Given an array, rotate the array to the right by k steps, where kis non-negative.
举个例子：
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
题目很好理解，实际上就是交换数组的两部分，只是换成“rotate k steps”的说法而已。等价于“把数组的最后 k 个元素和其他元素交换”。
一个细节区别就是，这里的 k 可以大于数组的长度，但只要让 k 与数组长度求模（余数）就行了，又转换成了“交换数组的两部分”这个问题。
下面来大开脑洞思考一下这个问题。如果你时间有限，可以跳过任一种思路，但不要错过最后的终极解法。
思路一，想办法构造一个环。
我觉得 LeetCode 这道题的描述实际上是在掩盖这个问题“交换数组的两部分”的本质，而且示例的 Explanation 也有点误导性质：因为我们都明白，如果在数组上按它的这个步骤一步一步的搬移元素，是一个十分笨拙低效的操作。
但是我们可以把这个数组转化成一个链表，然后把这个链表首尾相接，形成一个环，然后在适当的地方把这个环重新断开成为一个链表，最后把这个新得到的链表转换成数组，这个数组就是结果了。至于应该在什么地方重新断开这个环，跟 k 有关，相信你很容易就能想出来。
思路二，这个问题具有递归结构。
首先，如果交换的两部分元素数量一样（k == 数组长度 / 2），那么就比较简单，直接对应元素逐个互换就行了。（递归的 base case）
但是两部分元素如果不一样多，难点就来了，长的那部分交换会有剩余，这个剩余区域还需要和长区域经过交换的那个区域交换，以还原长区域的原始顺序，然后这个交换过程又会产生长短不一的问题，然后请重新阅读这段话。（递归调用）
很饶舌，画个图就能很容易理解了：
思路三，撑杆跳解法
思路一中也说了，一步一步搬移数组元素是很费事的，那干脆一步到位，直接把每个元素搬到它最终的位置上，显然这个最终位置和 k 有关。
画图理解一下，这个过程就像步长为 k 的撑杆跳：
这个解法是个很有意思的解法，看着注释应该不难理解，贴下代码：
void rotate(vector<int>& nums, int k) {
k %= nums.size();
int step = 0;
// 注意这个 for 的结束条件：每个元素都做了一次“撑杆跳”
// 即：每个元素都移到了最终位置
for (int start = 0; step < nums.size(); start++) {
int curr = start; // 初始起跳点
int prev_val = nums[start]; // 第一位准备起跳
do {
int next = (curr + k) % nums.size(); // 计算落地点
int temp = nums[next]; // 落地点的元素起开
nums[next] = prev_val; // 落地
prev_val = temp; // 下一位准备起跳
curr = next; // 更新起跳点
step++; // 撑杆跳完成次数+1
} while (curr != start);
}
}
思路四，终极解法
这个解法简单得让人诧异，只需要进行三次数组反转就行了：首先把数组的这两部分分别反转，然后把整个数组反转，就得到了答案。
这个解法简单的已经不需要贴代码理解了，算法重在理解思想。关于如何反转数组，很简单，而且编程语言都有内置的函数可以调用。
写在最后
其实，“交换数组的两部分”经过简单的变形，就变成了谷歌公司的一道面试题：给你一个英文句子字符串，对它进行完全倒装（不允许使用额外空间）。
比如说给面试者一句话：
A cycle of boom and bust.
请你倒装成：
bust and boom of cycle A.
原地倒装，不允许使用额外存储空间。
这个面试题问倒了不少面试者，因为正常人的思维总会陷入如何交换不同长度的单词，陷入复杂的条件判定和无限的细节中，这个人类看起来如此简单的问题对计算机来说似乎是个不可能完成的任务。但是你应该很容易想到解法：先把整个句子反转，再将每个单词分别反转，就得到了答案。
这种解法极其简单，但是如果没见过，基本不可能想出来。因为每一步反转操作都在将有意义的原始数据变得无序无意义，结果最后竟然能得到有意义的结果，这就十分违背人的直觉。
就像以前做数学题，但凡碰到需要作辅助线的题目，像我这种没见过类似题型的同学就要懵逼。因为我根本想不到，这些看似无意义的辅助线组合在一起竟然引出了题目中隐含的信息，柳暗花明又一村。
也许这就是计算机处理信息的独特方式：先把信息转换成其他形式再进行处理，但这种形式往往不是人所熟悉的。