数组题目复习Day2

209长度最小的子数组

暴力

首先想到的肯定是双层for循环，一次把所有的子集合全部看一遍，但是一看数据量绝对超时，于是按照昨天刷题的思想，利用双指针是否能够代替？
但是应该是使用不当，无法通过所有的用例，而且里面我写了一个if…else…应该是逻辑出现了问题

滑动窗口双指针思想

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;
        int minCnt = INT_MAX;
        for(int i=0,j=0;j<nums.size();j++){
            //i指向集合首元素， j指向集合尾元素
            sum+=nums[j];
            while(sum>=target){//注意这里是while
                minCnt = min(minCnt, j-i+1);
                sum-=nums[i];//一定是先减再++
                i++;
            }
        }
        if(minCnt == INT_MAX){
            return 0;
        }
        return minCnt;
    }
};

根本不用写if…else！
大了再判断就行，小了就一直向后+就可以
为什么里面是while而不是if?
因为如果在里面只进行一次的缩小，下一次就到外层for循环了，j还会往右走，但此时这个逻辑是错误的，while条件里的值一直不会小于target，而且在其中会漏算掉最小的个数
别忘记如果没找到对应的集合需要return 0，不要落下这个条件

时长：自己写30min写错了
看视频：10min
重新手撕：7min

59螺旋矩阵Ⅱ

好的，一到模拟就废🥲

遵循循环不变量

不能上一条边处理两个节点，下一条边只处理一个节点，再下一条边又一个节点都不处理了…
这样没有办法去进入循环，不整齐，没有规律，一定要每条边处理的大致相似
要定义好是左闭右开还是左闭右闭
在这里左闭右开是最好的选择

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n));//初始化的方式别写成n*n
        int cnt = 1;//用来计数存储矩阵值
        int startx=0,starty=0;//每一圈的起始位置
        int offset = 1;//偏移量
        int loop = n/2;//一共要转几圈

        while(loop--){
            int i=startx, j=starty;
            for(j;j<n-offset;j++){
                res[i][j] = cnt++;
            }
            for(i;i<n-offset;i++){
                res[i][j] = cnt++;
            }
            for(;j>starty;j--){
                res[i][j] = cnt++;
            }
            for(;i>startx;i--){
                res[i][j] = cnt++;
            }
            startx++;
            starty++;
            offset++;
        }
        if(n%2==1){
            res[startx][starty] = cnt;
        }
        return res;
    }
};

要记得n为奇数的时候手动补一下中间的数
我的错误点：
● res数组初始化弄错了，应该是两个参数，我直接n*n了
● while循环里的条件忘记–，而且还直接写成了n/2–(笑一下蒜了呢)
时间复杂度：O(n^2)

时长：自己做30~40min没做出来
看视频：18min
重新手撕：15min

区间和

简简单单一看就是前缀和，一眼暴力超时

#include<iostream>
using namespace std;
const int N = 1e5+10;
int nums[N];
int sum[N];
int main(){
    
    int n;
    cin >> n;
    int a, b;
    for(int i=1;i<=n;i++){
        cin >> nums[i];
        sum[i]+=nums[i]+sum[i-1];
    }
    while(cin >> a >> b){
        cout << sum[b+1] - sum[a] << endl;
    }
    return 0;
}