题目：
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
最直白（暴力）的解法是把数组中每个数都平方，再进行排序。但这样做的时间复杂度是O(nlogn)，于是乎尝试用双指针对其进行优化
思路：
如果数组内只有正数，那根本不需要排序，直接平方就搞定了，但数组中有正数和负数，就要引出双指针。
把数组想象成一个数轴，0在中间，左右是正负，我们知道数字离0越远（绝对值大），它的平方就越大。所以我们在数组左右都放上一个指针，对其平方进行比较。把较大的数字提出来，然后让左右指针向中间靠拢，就得到了一串从大到小排序的数字。再创建一个新的数组，从后往前依次将数字填进去，就达成了目标。
代码如下：
public static void main(String[] args) {
int[] arr = {-9,-5,0,1,2,4,6,7,9,10};
System.out.println(Arrays.toString(calc(arr)));
}
public static void main(String[] args) {
int[] arr = {-9,-5,0,1,2,4,6,7,9,10};
System.out.println(Arrays.toString(calc(arr)));//打印出目标数组
}
public static int[] calc(int[] arr){
int[] newArr = new int[arr.length];
int i = 0;
int j = arr.length - 1;
int k = j;
while (i<=j){
if(arr[i]*arr[i] > arr[j]*arr[j]){
newArr[k] = arr[i]*arr[i];
k--;
i++;
}else {
newArr[k] = arr[j]*arr[j];
k--;
j--;
}
}
return newArr;
}
这样的时间复杂度就是O(n)，简单了一些
代码还可以再优化一下（如newArr[k–] = arr[i]*arr[i]）但为了更简便的展示未做更改
接下来是代码的一些注意事项：
1.while语句可以换成for(i=0,j=0;i<=j;)，但要注意第二个分号后面的限制条件不需要写 arr[i]与arr[j]相比较，大的数字指针才会移动，写在for语句后面不好判断
2.while语句的i<=j，等于号不能漏掉。如果去掉了等于号，那么在i=j时循环就结束了，但arr[i]的元素并没有被成功排序，会漏掉一个数字。
3.while语句里的if判定，可以是>也可以是>=，当两个数相等的时候，自然拿出哪一个给k指针都没问题
977.力扣题目：有序数组的平方
代码随想录：有序数组的平方
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
和上题一样，先来看暴力解法：使用两个for循环嵌套，外部for循环控制起始位置，内部for循环找到终止位置，暴力解法代码如下：
public static void main(String[] args) {
int[] arr = {2,3,1,2,4,3};
System.out.println(Test01(arr, 7));
}
public static int Test01(int[] arr, int s){
int result = Integer.MAX_VALUE;//用来存储最小的数组长度，与length作比较
int sum = 0;
int length = 0;//目前的数组长度
for (int i = 0; i < arr.length; i++) {
sum = 0;
for (int j = i; j <arr.length; j++) {
sum= sum +arr[j];
if(sum >=s){
length = j - i + 1;
result = Math.min(length,result);
break;//已经找到符合长度的数据，结束内部循环
}
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
这样的时间复杂度为O(n^2)，我们需要尝试减少时间复杂度，优化的思路和双指针类似。
用一个for循环来控制一个指针从左往右走，再在数组第一位（0）放一个左指针，计算两个指针之间的数据相加，如果相加超过了s，就把左指针往右移，并记录当前的窗口（即左右指针包裹的范围）长度，与当前存储的result作比较，存入较小值
public static void main(String[] args) {
int[] arr = {2,3,1,2,4,3};
System.out.println(Test01(arr, 7));
System.out.println(Test02(arr,7));
}
public static int Test02(int[] arr, int s){
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
int length = 0;
for (int right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum >= s){
length = right - left + 1;
result = Math.min(result,length);
sum -= arr[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
这样的时间复杂度就是O(n)，优化成功
记一些注意事项&解答：
904.力扣相关题目
76.力扣相关题目
代码随想录：长度最小的子数组
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
这道题有一点绕，但只要处理好边界，不是很难。
首先看到这道题就会想到用循环解决，但要保证每个循环要干的事是一样的，比如这样一个二维数列
[1 2 3]
[8 9 4]
[7 6 5]
我们对每一行每一列的处理都应该保持一致，比如先填充1和2，在最后一列填充3和4，在最后一行填充5和6，这样一个左闭右开的处理方式。也就是说，每一行/列都要留最后一个空白，所以我们引入一个变量offset。
然后，以一圈为一个循环，来看总共要转多少圈才能完成填充。用草稿纸画一下，会发现4x4的矩阵需要转2圈，3x3的矩阵需要转一圈（但是中间是个空白），得出：循环次数=n/2，如果n为奇数，则需要在中间补上一个数
把这样的二维数组看成矩阵，写成arr[i][j]的形式
int[][] arr = new int[n][n];
int start = 0;//起始位置
int offset = 1;//为了控制循环条件一致而保留的位置
int i = 0;
int j = 0;
int count = 1;//计数用
for(;j<n - offset;j++){
arr[start][start] = count++;
}
第一个循环结束，此时矩阵为[1,2,0][0,0,0][0,0,0]
开始第二个循环，这个时候应该改变i的位置。注意这里我把i和j放在了循环外面，经历完第一个循环后，此刻j=2，刚好在[1,2,0]的“0”处，继续代码：
for(;i < n - offset;i++){
arr[i][j] = count++;
}
此刻矩阵为：[1,2,3][0,0,4][0,0,0]
以此类推，第三个循环应该是arr[i][j]，限制条件为j>=循环次数，使用j–；最后一个循环不再赘述，基本一致
跑完一圈后，如果有第二圈（即n>=4），应该把startX和startY都进行递增，把offset也进行递增
以n=4举例：跑完一圈后的矩阵为：
[1,2,3,4]
[12,0,0,5]
[11,0,0,6]
[10,9,8,7]
此刻第二圈的起始位置是[1][1]，应该对start进行递增。同样根据左闭右开的原则，应该只填充一个位置，所以for循环的限制为i<n-offset（即i<2，只执行一次）
到这里代码基本完成，最外层加上while循环判断次数，以及遇到n为奇数时加一行代码：n[i][j] = count;
最终代码如下：
public static int[][] Test(int n){
int loop = 0;//当前的循环次数
int[][] arr = new int[n][n];
int start = 0;//起始位置
int offset = 1;//为了控制循环条件一致而保留的位置
int i = 0;
int j = 0;
int count = 1;
while (loop++<n/2) {
for(j = start;j < n - offset;j++){//此循环控制上面一行
arr[start][j] = count++;
}
for(i = start;i < n - offset;i++){//此循环控制右边一列
arr[i][j] = count++;
}
for(;j>=loop;j--){//此循环控制下面一行
arr[i][j] = count++;
}
for(;i>=loop;i--){//此循环控制左边一列
arr[i][j] = count++;
}
start++;
offset++;
}
if(n%2 == 1){
arr[i][j] = count;
}
return arr;
}
其实还可以进行优化，比如循环里的offset都可以换成n-loop，但为了更加直观所以没进行更改
一些注意事项：
今日学习时间：1h+1h+2h