1.给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
- 示例 1：
- 输入：nums = [-4,-1,0,3,10]
- 输出：[0,1,9,16,100]
- 解释：平方后，数组变为 [16,1,0,9,100]
- 排序后，数组变为 [0,1,9,16,100]
解析：这道题可以通过双指针来求解，即给定i和j，分别指向0位置和numsize -1的位置， 比较两个指针所指向的元素的平方的大小，大的逆序放在要返回的数组中。为什么要逆序呢？
由于已知数组是非递减顺序排序的：
假如输入的数组全是非负数，那么平方后也是一个递增顺序。
假如输入的数组全是负数，那么平方后是一个递减的顺序。
假如输入的数组有负数，有非负数，那么平方后的情况就尾部是递减或递增的。
所以逆序存放平方后大的元素，就不再需要讨论上面的情况。
图解如上：
这样就可以解决问题了。
代码如下：
int* sortedSquares(int* nums, int numsSize, int* returnSize) { assert(nums); *returnSize = numsSize; int *ret = (int*)malloc(sizeof(int)*numsSize); int i =0; int j =numsSize -1; while(numsSize--) { if(nums[i]*nums[i]<nums[j]*nums[j]) { ret[numsSize] = nums[j]*nums[j]; j--; } else { ret[numsSize] = nums[i]*nums[i]; i++; } } return ret; }
2.给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: 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]
对于旋转的题目，只需要记住最优解法即可。
最优解是：逆序
该方法远比双指针来得更加简单粗暴。
- 后k个逆序
- 前numsSize个逆序
- 整体逆序
想想是不是这样。
所谓的逆序，也是第一个下标的元素和最后一个下标的元素交换位置即可
交换完第一个和最后一个元素后，再交换第二个元素和倒数第二个元素，以此类推
代码实现：
void reverse(int*left,int *right) { while(left<right) { int tmp = *left; *left = *right; *right = tmp; left++; right--; } } void rotate(int* nums, int numsSize, int k) { if(numsSize==1) { reverse(nums,nums); } else if (numsSize ==2) { if(k%2!=0) { reverse(nums,nums+1); } else reverse(nums,nums); } else { k%=numsSize; reverse(nums+numsSize-k,nums+numsSize-1);//后k个逆序 reverse(nums,nums+numsSize-k-1);//前numsSize -k reverse(nums,nums+numsSize-1);//整体 } } 2.
k%=numsSize的原因是，假如旋转8次，有6个元素，其效果和旋转两次是一样的。
3.给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
输入: nums = [0,1,0,3,12] 输出:[1,3,12,0,0]
解析：
本题使用双指针也是非常好的方法。
给一个指针指向下标0位置，该指针用来记录非0元素的个数，给另一个指针，该指针一次次往后遍历，如果往后遍历的指针！= 0 ，那么就把这个元素赋值给第一个位置的元素，然后各自往后移。
如果往后遍历的指针 == 0，那么继续往后遍历，第一个指针不用走。
这样遍历下去，最后第一个指针指向的位置就是最后一个非0元素的下标，然后把 后面的元素全都赋值成0即可。
代码如下：
int cmp(const void*e1,const void*e2) { return *(int*)e1 - *(int*)e2; } void moveZeroes(int* nums, int numsSize) { assert(nums); int i =0; int j =0;//记录0个数 for(i=0;i<numsSize;i++) { if(nums[i]!=0) { nums[j++] = nums[i]; } } while(j<numsSize) { nums[j++] = 0; } }
4.给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
解析：
在这道题中，我们要寻找的是符合条件的一对下标 (i,j)它们需要满足的约束条件是：
i、j都是合法的下标，即 0≤i
i
而我们希望从中找到满足 arr[i] + arr[j] == target 的下标 (i,j)。以 n=5 为例，这时候全部的搜索空间是：
我们从右上角开始比较：
当arr[0] +arr[4] >target时，此时arr[0]是所在行中最小的，既然最小的+arr[4] 都> target，那么后面的arr[1]+ arr[4] ,arr[2] + arr[4] ...都大于target，所以应该找arr[0] +arr[3]的元素 ，此时就可以排除一列元素了，即j--。如下图：
当arr[0] +arr[4]
arr[0]+arr[2]...也仍然小于target。所以应该排除掉一行元素，即i++。如下图：
代码如下：
1. int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){ *returnSize = 2; assert (numbers); int i =0; int j =numbersSize -1; int *ret = (int*)malloc(sizeof(int)*(*returnSize)); while(i<j) { if(numbers[i]+numbers[j]<target) { i++; } else if(numbers[i]+numbers[j]>target) { j--; } else { ret[0] = i+1; ret[1] = j+1; return ret; } } ret[0] = -1; ret[1] = -1; return ret; }
