引言：某些数据结构题目，对一些新上手的小白很不友好，这里推荐一种“笨方法” ：空间换时间
思路：利用额外开辟的空间，增加空间复杂度，去减少传统暴力求解的时间开销
举例：
189. 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出:[5,6,7,1,2,3,4]解释: 向右轮转 1 步:[7,1,2,3,4,5,6]向右轮转 2 步:[6,7,1,2,3,4,5]向右轮转 3 步:[5,6,7,1,2,3,4]
观察解释，可知题目中给的思路是暴力求解法
一、空间换时间法：将需要逆序的前半段传给另一个空间的后半段，后半段传给前半段
void rotate(int* nums, int numsSize, int k) {
k %= numsSize;
int* p = (int*)malloc(sizeof(int) * numsSize); //额外开辟空间
memcpy(p + k, nums, (numsSize - k) * sizeof(int)); //dest src num（字节数）
memcpy(p, nums + numsSize - k, k * sizeof(int));
memcpy(nums, p ,sizeof(int) * numsSize);
// nums = p; //不允许！ 将p释放之后，nums指向的内容变成随机值
free(p);
p = NULL;
}
//此时的空间复杂度为O（N） //额外用malloc开辟了4 * numsSize个字节的空间
二、最优解：三段逆置法
思路：（题目已经提示你，轮转数组！！！）
1.先反转整个数组
2.再反转数组的 1~K 项
3.再反转 K~numsSize 项
4.得到结果
void reverse(int* p, int left, int right) //为了第三次旋转，需要自己传左右位置
{
//对两端进行操作的时候，一般定义left 和 right 作为下标
while(left < right) // < 不是 <=
{
int tmp = p[left]; //解引用可以对实参内容进行修改
p[left++] = p[right];
p[right--] = tmp;
}
}
void rotate(int* nums, int numsSize, int k) { //void 不需要返回
k %= numsSize; // K 的大小，可能会长于字符串长度（ K %= numsSize,可以按照周期性的方式，减去字符串长度的整数倍，留下真正需要操作的旋转数）
reverse(nums, 0, numsSize - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, numsSize - 1);
}
//此时空间复杂度为O（1）
//三个reverse空用同一个空间，每个reverse额外开辟的空间为常数个。 一般只进行常数个变量开辟时，空间复杂度都是O（1）
