LeetCode代码随想录（二）——977.有序数组平方、209长度最小子数组、59螺旋矩阵2

目录

一、977有序数组平方

二、209长度最小子数组

三、59螺旋矩阵2

一、977有序数组平方

要求将一个数组的元素平方之后的数按照大小进行排列（注意数组当中有负数）

思路：（1）平方之后再挨个比较排序，时间复杂度nlog（n），pass掉

（2）由于有负数，所以平方之后的最大数肯定是在数组的两侧出现的，那么我们就可以从两侧找，最大的那个就放进新的数组里，但是题目要求的是从小到大排序，为了不让排序完再倒一遍就直接用数组最后一个去装第一个找到的最大的数，依次装入（因为知道数组总长度）

var sortedSquares = function(nums) {
    let k=nums.length
    let array=[]
    for(let i=0,j=k-1;i<=j; ){
        if(nums[i]*nums[i]>=nums[j]*nums[j]){
            array[k-1]=nums[i]*nums[i];
            k--;
            i++;
        }else{
            array[k-1]=nums[j]*nums[j];
            k--;
            j--;
        }
    }
    return array;
};

首先要注意for循环中第三块不是i++或者j--，因为是取了左边才i++，取了右边才j--

二、209长度最小子数组

题目是在一个正整数的数组中，找到这一段元素的和大于等于s的一段连续的最小长度的区间

思路：双指针｜滑动区间，两个指针一个指向起始位置，一个指向终止位置，但是终止位置最开始就固定在末尾的。

首先i（起始）、j（末端）都在数组0位置，然后j依次向后移，同时sum+=，直到sum和大于等于s之后进入循环，此刻这个终止位置就固定了，i开始左移，左移完之后的sum不是重新计算，而是减去移动完的那些项 并且i++。

最终会到达一个j不动、i 动的大于等于s的最小长度。

然后j再开始向后移动···

var minSubArrayLen = function(target, nums) {
   let j=0;//终止指针，虽然是终止指针但是不是固定不动的
   let sum=0;
   let i=0;
   let flag=0;
   let minLength=nums.length
   for(j=0;j<nums.length;j++){
    sum+=nums[j]
    while(sum>=target){
        flag=1;
        minLength=Math.min(j-i+1,minLength)
        sum-=nums[i]
        i++;
    }
   }
   if(flag==0) minLength=0;
   return minLength;
};

注意数组中可能所有项加起来都小于s，我设置了一个标识（flag）记录有没有大于等于s过，最后返回最小长度minLength。

三、59螺旋矩阵2

思路：其实就是按照每一行左闭右开去标记，比较麻烦的是数组number里的横纵跟坐标系是反着的，所以我在做的时候到了for循环那里我先把这一行要遍历的坐标写下来，这样更好观察是i还是j变化。

而且我在做的时候是根据例题要求n=3进行的，所以在后面两个for循环里判断条件都是写的>0，导致n=4情况错误（offset的作用），这个时候就画一下图（圈数较多的情况），把外层/边界点用表达式标出来就能比较直观的解决了。

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let count=1;
    let startx=0;
    let starty=0;
    let offset=1;
    let loop=Math.floor(n/2);
    let number = Array.from({ length: n }, () => Array(n).fill(0));
    while(loop--){
        let i=startx;
        let j=starty;
        for(;j<n-offset;j++){
            number[i][j]=count++;
            //j最后等于n-offset=2
            //(0,0)(0,1)
        }
        for(;i<n-offset;i++){
            number[i][j]=count++;
            //j依旧是n-offset 2；i最后等于n-offset 2
            //(0,2)(1,2)
        }
        for( ;j>starty;j--){
            number[i][j]=count++;
            //i不变还是n-offset 2；j最后等于0
            //（2，2）（2，1）
        }
        for(;i>startx;i--){
            number[i][j]=count++;
            //i最后等于0；j也等于0
            //(2,0)(1,0)
            //一圈完成
        }
        offset++;
        startx++;
        starty++;
    }
    if(n%2===1){
        let k=Math.floor(n/2);
        number[k][k] = count;
    }
    return number;
};