代码随想录第2天|LeetCode 977有序数组的平方||209 长度最小的子数组||59 螺旋矩阵 II

第一章 数组part02

今���花费时间较多，在第二题的边界判定上消耗时间较多，应多注重细节。

LeetCode 977 有序数组的平方Easy

题目链接： 977 有序数组的平方

思路:1. 考虑到数组可能有负数有正数，它们的平方的大小都是从两边到0逐渐减小，所以可以设置两个指针从两边到中间运动，不断判断指针位置处两个数的大小，将较大的数从后往前放入数组res中。

完整C++代码如下：

//时间复杂度：O(1)//空间复杂度：O(1)class Solution {public:    vector sortedSquares(vector& nums) {        int len=nums.size();  int l=0,r=len-1;        vector res(len);while(l            if(abs(nums[r])=abs(nums[l])){                res[--len]=nums[r]*nums[r--];                            }else{                 res[--len]=nums[l]*nums[l++];            }        }        return res;    }};

LeetCode 209 长度最小的子数组

题目链接：209 长度最小的子数组

思路：

1. 滑动窗口（双指针）：由于是求一个长度最小的连续子数组，所以想到使用双指针逐渐缩小范围，但从两边到中间不断缩小，两端指针指向比较大小保留较大值的思路是错误的，原因在于本题局部最大值保留未必全局最优连续子数组保留，如下面若取target为13，即使l为2，仍然要保留r,让l+1

   仍然采取双指针的思路，重点是要考虑每种（恰好或多一点）符合条件组合中的最小值*（直接考虑整体而不是两端逐个比较），让两个指针l,r都置于最左边，优先让r右移直到恰好满足target,r停止移动，此时l开始移动直到l,r之间的数组*恰好不满足target，r继续右移，每完成一轮r,l指针移动得到的连续子数组就是所有组合中的一组，通过一个数minLen记录最小长度。

   注：双指针（滑动窗口）的思路是暴力解思路的简单优化，就是找所有的可能组合，但1. 滑动窗口可以实时的用两个指针维护结果，而暴力双for需要不断重新计算sum。2. 一些可能不需要再进行计算，双for仍会从头开始依次遍历0，双指针中l会直接后移到5。

完整C++代码如下：

//时间复杂度：O(n)//空间复杂度：O(1)class Solution {   public:    int minSubArrayLen(int target, vector& nums) {int l=0,r=0;        int sum=nums[0];//默认直接存第一个数        int min_len=nums.size()+1;while(1){            if(sum                if(r=nums.size()-1){//已经到最后一位了，这时候如果再次进入sum                if(r-l+1public:    vectorvector            i=startX;//每一圈的起始x与起始y            j=startY;              //上行从左到右            for(j=startY;j                res[i][j]=numNow++;            }            //右列从上到下            for(i=startX;i                res[i][j]=numNow++;            }            //下行从右到左            for(;jstartY;j--){                res[i][j]=numNow++;            }            //左列从下到上            for(;istartX;i--){                res[i][j]=numNow++;            }            EndPosition--;            startX++;            startY++;        }        //考虑奇数矩阵最后中心的数也要填充，不用再设置别的数，此时的startX，Y恰好位于此处        if(n%2){            res[startX][startY]=numNow;        }        return res;    }};