Day02

今日任务：

• 977 有序数组的平方
• 209 长度最小的子数组
• 59 螺旋矩阵Ⅱ

977 有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

双指针问题，以及数组本身时有序的；

思路：

1. 左、右两个指针，比较两边的平方数，将较大的数从后往前放进新生成的数组
2. 若左边的平方数 大于 右边的平方数，则需要将左边的指针向右移动一格
3. 若左边的平方数 小于 右边的平方数，则需要将右边的指针向左移动一格
4. 直到两个指针指向同一个位置，就是最小的那一个，将平方数放进数组后，退出

class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int[] res = new int[n];int left = 0, right = n - 1;while(left <= right) {if(nums[left] * nums[left] <= nums[right] * nums[right]) {res[--n] = nums[right] * nums[right];right--;}else {res[--n] = nums[left] * nums[left];left++;}}return res;}
}

209 长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/description/

暴力遍历的话，时间超市；

滑动窗口问题，就是不断的调节子序列的起始位置和终止位置

思路：

1. 如果当前窗口的值大于等于 target 了，窗口的后面就要向前移动了，前面保持不动
2. 如果当前窗口的值小于 target 了，窗口的后面保持不动，前面向前移动
3. 每次满足条件的时候都需要进行比较 res 的值，选择较小者

class Solution {public int minSubArrayLen(int target, int[] nums) {int n = nums.length;if(n == 0) {return 0;}int res = Integer.MAX_VALUE;int start = 0, end = 0;int sum = 0;while(end < n) {sum += nums[end];while(sum >= target) {res = Math.min(res, end - start + 1);sum -= nums[start];start++;}end++;}return res == Integer.MAX_VALUE ? 0 : res;}
}

59 螺旋矩阵Ⅱ

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

关键还是在转圈的逻辑，以及四个边界的变化情况

class Solution {public int[][] generateMatrix(int n) {int l = 0, r = n -1, t = 0, b = n - 1;int[][] mat = new int[n][n];int num = 1, tar = n * n;while(num <= tar) {for(int i = l; i <= r; i++) mat[t][i] = num++;t++;for(int i = t; i <= b; i++) mat[i][r] = num++;r--;for(int i = r; i >= l; i--) mat[b][i] = num++;b--;for(int i = b; i >= t; i--) mat[i][l] = num++;l++;}return mat;}
}