day02 有序数组的平方 长度最小子数组 螺旋矩阵

题目1：977? 有序数组的平方

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

题意?

返回非递减整数数组的每个数字的平方和? 也按照递减排序

双指针★

代码

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

时间复杂度O(n)

空间复杂度O(n)

暴力解法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i = 0;i < nums.size();i++){
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(), nums.end());//排序
        return nums;
    }
};

时间复杂度O(n+nlogn)

题目2：209? 长度最小的子数组

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

题意

数组中含有n个正整数，返回数组中总和大于等于target的长度最小的连续子数组的长度，注意数组中一定要是正整数，因为只有正整数才会越加越大，如果没有则，返回0

滑动窗口★

思想：不断更新连续子数组的起始位置和终止位置，使用1个for循环就可以完成这些操作

for循环中的变量应该是终止位置，这样才能避免暴力解法两层for循环的情况

滑动窗口移动的条件：当前窗口的值大于等于s

遇到某个滑动窗口内的总和大于等于target，就移动这个滑动窗口的起始位置，看是否还有更短的长度的子数组满足大于等于target的条件；如果滑动窗口内的总和小于target，说明整个滑动窗口扩充的还不够长，于是需要移动终止位置

代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i = 0;//滑动窗口起始位置
        int sum = 0;//总和
        int subL = 0;//子数组长度
        int result = INT32_MAX;
        for(int j = 0;j < nums.size();j++){
            sum += nums[j];  //子数组总和
            while(sum >= target){
                subL = j - i + 1;
                result = min(result,subL);
                sum -= nums[i];//将起始位置的数值从总和中减去
                i++; //注意同时移动起始位置
            }
        }
        return result==INT32_MAX ? 0 : result;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

暴力解法

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX;
        int subL = 0;
        for(int i = 0;i < nums.size();i++){
            int sum = 0;
            for(int j = i;j < nums.size();j++){
                sum += nums[j];
                if(sum >= target){
                    subL = j - i + 1;
                    result = min(result,subL);
                    break;//此处跳过for循环是因为数组中都是正整数，越往后加数值肯定越大，越满足sum>target
                }
            }
        }
        return result==INT32_MAX ? 0 : result;
    }
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

使用暴力解法会超时，如下图

题目3：59 螺旋矩阵Ⅱ

题目链接：59.螺旋矩阵Ⅱ

题意

正整数1~n^2的所有元素，按照顺时针排列成n*n的正方形矩阵，并按照矩阵的形式一行一行的输出

循环不变量

本题还是要坚持循环不变量原则，每一圈的处理规则要统一，均是左闭右开，由外向内一圈一圈画，每一圈都可以使用一套代码，每一圈的每一条边的情况列出来，遍历圈数

使用左闭右开的原则，即拐角处的元素放到下一条边处理? ? i代表行，j代表列

转的圈数是 n/2? 的原因是：将整个正方形对半分，看一半有多少条边，就可以转多少圈

代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
       vector<vector<int>> nums(n,vector<int>(n,0));
       int startx = 0;  //i的起始位置
       int starty = 0;  //j的终止位置
       int offset = 1;  //第一圈的偏移量
       int count = 1;   //每个位置的数，计数，不断累加
       int loop = n / 2;  //圈数
       int mid = n / 2;  //中间的位置
       int i,j;
       while(loop--){
           //上行   i代表行,j代表列   行不变，列++
           for(j = starty;j < n - offset;j++){
               nums[startx][j] = count++;//跳出循环时，i=startx,j=n-offset
           }
           //右列    行++，列不变
           for(i = startx;i < n - offset;i++){
               nums[i][j] = count++; //跳出循环时，i=n-offset,j=n-offset
           }
           //下行    行不变，列--
           for(;j > starty;j--){
               nums[i][j] = count++;//跳出循环时，i=n-offset,j=0
           }
           //左列    行--，列不变
           for(;i>startx;i--){
               nums[i][j] = count++;//跳出循环时,i=0,j=0
           }
           //进入下一圈做准备
           startx++;
           starty++;
           offset++;
       }
       if(n % 2 == 1) {
           nums[mid][mid] = count;  //这里不是i,j因为是i和j的话，指向的是最后一圈的第一个位置，不符
       }
       return nums;
    }
};

• 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
• 空间复杂度 O(1)