977.有序数组的平方
题目：
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 ：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
解题思路：
1. 暴力解法
最简单的方法就是每个数平方之后排序，一行代码就可以搞定。
var sortedSquares = function (nums) {
return nums.map((item) => item * item).sort((a, b) => a - b)
};
2. 双指针
数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。因此可以从大到小来找对应的元素，找到后把指针前移，循环终止条件是 left > right，这里还需要注意一点就是初始化数组的方式。
var sortedSquares = function (nums) {
let count = nums.length - 1;
const arr = new Array(nums.length).fill(0);
let left = 0;
let right = count;
while(left <= right){
if(nums[left] * nums[left]>=nums[right] * nums[right]){
arr[count--] = nums[left] * nums[left];
left++;
}else{
arr[count--] = nums[right] * nums[right];
right--;
}
}
return arr;
};
209.长度最小的子数组
题目：
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
解题思路：
1. 暴力解法
两层for循环，外层记录起始位置，内层记录终止位置，一旦在内层找到满足条件的就break此时一定是当前循环的最小值。
var minSubArrayLen = function (target, nums) {
let minLen = Infinity;
let sum = 0
for (let i = 0; i < nums.length; i++) {
sum = 0
for (let j = i; j < nums.length; j++) {
sum += nums[j];
if (sum >= target) {
const curLen = j - i + 1;
minLen = curLen < minLen ? curLen : minLen;
break;
}
}
}
return minLen === Infinity ? 0 : minLen
};
2. 滑动窗口
这类解法的特点在于用一次循环就解决之前暴力解法需要两轮for循环的问题。
需要考虑三个问题：
- 窗口范围：窗口内是满足其和 ≥ s 的长度最小的连续子数组。
- 窗口结束位置 j：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
- 窗口起始位置 i：如果当前窗口的值大于s了，窗口就要向前移动了。这里还要注意窗口起始位置移动需要再while循环里移动，因为有可能在 s = 5, nums = [1, 1, 1, 1, 5] 的情况，这时虽然已经在 j = 4 的情况下第一次出现了 sum ≥ 5 的情况，但这个时候 i 仍然可以不断向前移动，缩小区间。
var minSubArrayLen = function (target, nums) {
let minLen = Infinity;
let sum = 0
let i = 0;
for (let j = 0; j < nums.length; j++) {
sum += nums[j]
while (sum >= target) {
const curLen = j - i + 1;
minLen = curLen < minLen ? curLen : minLen;
sum -= nums[i]
i++;
}
}
return minLen === Infinity ? 0 : minLen
};
59.螺旋矩阵II
题目：
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例.png
示例：
输入: 3
输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
解题思路：
1. 记录四条边所在的位置
在这种解法中分别定义 top、bottom、left、right 四条边所在的初始位置，然后依次进行模拟，下面以 三阶矩阵 为例来讲解。
- 对于top ，top行不变，记录从左到右的序号，然后把top向下移动。
[ [ 1, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
[ [ 1, 2, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
[ [ 1, 2, 3 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
- 对于 right，right列不变，记录从上到下的序号，然后把right向左移动。
[ [ 1, 2, 3 ], [ 0, 0, 4 ], [ 0, 0, 0 ] ]
[ [ 1, 2, 3 ], [ 0, 0, 4 ], [ 0, 0, 5 ] ]
-对于bottom，bottom行不变，记录从右到左的序号，然后把bottom向上移动。
[ [ 1, 2, 3 ], [ 0, 0, 4 ], [ 0, 6, 5 ] ]
[ [ 1, 2, 3 ], [ 0, 0, 4 ], [ 7, 6, 5 ] ]
-对于left，left列不变，记录从下到上的序号，然后把left向右移动。
[ [ 1, 2, 3 ], [ 8, 0, 4 ], [ 7, 6, 5 ] ]
此时四个边的值分别为1、1、1、1，所以再执行一次top的循环就会实现矩阵。
[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
代码如下：
var generateMatrix = function (n) {
const matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
let top = 0;
let bottom = n - 1;
let left = 0;
let right = n - 1;
let cur = 1;
while (cur <= n * n) {
for (let i = left; i <= right; i++, cur++) {
matrix[top][i] = cur
}
top++;
for (let i = top; i <= bottom; i++, cur++) {
matrix[i][right] = cur
}
right--;
for (let i = right; i >= left; i--, cur++) {
matrix[bottom][i] = cur
}
bottom--;
for (let i = bottom; i >= top; i--, cur++) {
matrix[i][left] = cur
}
left++;
}
return matrix;
};
2. 记录每轮的偏移量offset
这种方法遵循 左闭右开 原则，每轮对一圈进行操作，并且区分奇偶数。
var generateMatrix = function (n) {
const matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
let loop = Math.floor(n / 2);
let mid = Math.floor(n / 2);
let count = 1;
let offset = 1;
let startx = 0;
let starty = 0;
while (loop--) {
let i = startx;
let j = starty;
for (j = startx; j < n - offset; j++) {
matrix[startx][j] = count++;
}
for (i = startx; i < n - offset; i++) {
matrix[i][j] = count++;
}
while (j > starty) {
matrix[i][j] = count++;
j--;
}
while (i > startx) {
matrix[i][j] = count++;
i--;
}
startx++;
starty++;
offset += 1;
}
if (n % 2) {
matrix[mid][mid] = count;
}
return matrix;
};
注意点：
- 二维数组的初始化方式：
const matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));
- 第一种方式不需要区分奇偶，第二种方式需要。
