LeetCode刷题笔记（Day3）【滑动窗口+螺旋矩阵】

题号：

• 209.长度最小的子数组 力扣题目链接

        【注意】：数组所有元素之和都小于target时，要设置返回0，否则会返回INT_MAX 

• 904.水果成篮
• 76.最小覆盖子串 【T中字符不按顺序出现也算，T中可能包含重复字符】

                76 有示例没过去，贴在文章后面啦，希望有大佬可以解惑

• 59.螺旋矩阵II 力扣题目链接

                Q1：边界如何处理？保持处理区间左闭右开【遵循循环不变量原则】

                Q2：转几圈？n/2圈

                Q3：当n%2==1时，填补中心位置（n/2,n/2）=count；

常用string函数：

76未AC代码：

class Solution {
public:
    bool check(string a, string b){//检查a中是否包含b
        std::vector<int> an(200);
        std::vector<int> bn(200);
        for(int i = 0; i < a.size(); i ++){
            an[int(a[i])] ++;
        }
        for(int i = 0; i < b.size(); i ++){
            bn[int(b[i])] ++;
        }
        for(int i = 0; i < 99; i ++){
            if(an[i] < bn[i]) return false;
        }
        return true;
    }


    string minWindow(string s, string t) {
        string res = "";//存储结果
        int left = 0;//左指针
        string ans = "";//存储中间状态
        int La = 0;//ans长度
        int Lr = INT_MAX;//res长度
        for(int right = 0; right < s.size(); right ++){
            ans = s.substr(left, right - left + 1);//取窗口中的字符串作为中间状态
            cout<<"ans1:"<<ans<<endl;
            while(check(ans, t)){//ans包含t时，检查窗口是否可以缩小，left右移
                La = ans.size();
                if((La < Lr) && (check(ans, t))){//如果ans满足条件，先存储在res中
                    res = ans;
                    Lr = res.size();
                }
                left ++;//窗口右移
                if (left > right) break;//【防止substr右溢出】
                ans = s.substr(left, right - left + 1);//ans更新
                cout<<"ans2:"<<ans<<endl;
                cout<<"res:"<<res<<endl;
            }
        }
        return res;
    }
};

测试结果：