977、有序数组的平方

·双指针思想

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

前提：按非递减顺序排序的整数数组
   （存在重复值）
   可能存在负数

思路：负数平方后，数组元素大小会变成两头大中间小。
   适合双指针进行比较两头大小
   数组从尾巴开始排起比较方便

方法：双指针法
   时间复杂度O(n);
   空间复杂度O(n);

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int t=nums.size()-1;
        vector<int> nums2(nums.size(),0);
        int j=0;
        for(int i=t;i>=0;i--){
            if(nums[j]*nums[j]>=nums[t]*nums[t]){
                 nums2[i]=nums[j]*nums[j];
                j++;
            }
            else{
                nums2[i]=nums[t]*nums[t];
                t--;
            }
        }
        return nums2;
    }
};

收获摘要：一开始考虑能不能不建新数组，不创建新数组的话，双指针走过去会出现数组覆盖情况doge

学习的文章链接：https://programmercarl.com/0977.有序数组的平方.html
学习的视频链接：https://www.bilibili.com/video/BV1QB4y1D7ep

209、长度最小的子数组

·双指针思想（滑~ 动~ 窗口）

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

前提：最小连续子数组
   >=target

思路：依旧是双指针~循环节是尾巴指针
   双指针形成一个区间，就是滑~ 动~ 窗口

方法：双指针优化了暴力解法：两层循环O(n^2)
   时间复杂度O(n);
   空间复杂度O(1);

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int l=nums.size();
        int c=0;
        int min=l+1;
        int i=0;
        int j=0;
        long s=0;
        while(i<l){//尾巴指针      
            s=s+nums[i];
            c++;
            while(s-nums[j]>=target){//缩短头指针，使得子数组长度尽可能地小
                s=s-nums[j];
                c--;
                j++;
            }
            if(s>=target&&c<min)min=c;
            i++;
        }
        if(min==l+1)min=0;
        return min;
    }
};

收获摘要：双指针的优化很巧妙！省去了多余的比较

学习的文章链接：https://programmercarl.com/0209.长度最小的子数组.html
学习的视频链接：https://www.bilibili.com/video/BV1tZ4y1q7XE

59、螺旋矩阵Ⅱ

·边界模拟

怎么也飞不出~ 螺旋的世界~

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

思路：注意边界！！仔细再仔细，边界上的数组下表要仔细算！

方法：模拟法
   时间复杂度O(n^2);
   空间复杂度O(n^2);

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int count=0;
        int loop=n/2;
        vector<vector<int>> nums(n,vector<int>(n,0));
        int x0=0;
        int j;
        while(loop>0){
            for(j=x0;j<=n-x0-2;j++){
                count++;
                nums[x0][j]=count;
            }
            for(j=x0;j<=n-x0-2;j++){
                count++;
                nums[j][n-x0-1]=count;
            }
            for(j=n-x0-1;j>=x0+1;j--){
                count++;
                nums[n-x0-1][j]=count;
            }
            for(j=n-x0-1;j>=x0+1;j--){
                count++;
                nums[j][x0]=count;
            }
            x0++;
            loop--;
        }
        if(n%2==1)nums[x0][x0]=n*n;
        return nums;
    }
};

收获摘要：for循环一层层模拟，主要是螺旋后每一层的数组的值和下标发生了变化

学习的文章链接：https://programmercarl.com/0059.螺旋矩阵II.html
学习的视频链接：https://www.bilibili.com/video/BV1SL4y1N7mV/

学习时长：4h

原文地址：http://www.cnblogs.com/tinct/p/16834336.html