经典面试题之滑动窗口专题

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 长度最小的子数组 
        // 大于等于 target
        int min_len = INT32_MAX;
        // 总和
        int sum = 0;
        int start  = 0; // 起点
        for(int i = 0; i< nums.size(); i++) {
            sum += nums[i];
            while(sum >= target) {
                int len = i-start+1;
                if(len < min_len ) {
                    min_len = len;
                } 
                sum -= nums[start++];
            } 
        }
        if(min_len == INT32_MAX ) {
            return 0; 
        } else {
            return min_len;
        }
    }
};

3. 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 长度
        int str_size = s.size();
        if(str_size == 0) {
            return 0;
        }
        int max_len = 0;
        int left = 0;
        unordered_set<char> str; // 用来存储 字符
        for(int i = 0; i< str_size ; i++ ){
            
            // 如果没有找到 该字符
            while(str.find(s[i]) != str.end()) {
                str.erase(s[left]);
                left++;
            }
            max_len = max(max_len, i- left + 1);
            // 插入
            str.insert(s[i]);
        }
        return max_len;
    }
};

76 最小覆盖子串

class Solution {
public:
    unordered_map<char,int> tstr, sstr;

    bool check() {
        for(auto tchar : tstr) {
            if(tchar.second > sstr[tchar.first]) {
                return false;
            }
        }
        return true;
    }


    string minWindow(string s, string t) {
        int n1 = s.size();
        int n2 = t.size();
        if(n1 < n2) return "";
        int len = INT_MAX;
        int ans_left = -1; // 最小窗口的左边界
        // 构建哈希表
        for(auto tchar : t) {
            tstr[tchar]++;
        }
        int left = 0;
        int right= 0;
        for(int right = 0; right < n1; right++) {
            sstr[s[right]]++; // 添加
            // 说明找到 该字符
            if(tstr.find(s[right]) != tstr.end()) {
                // 这里是对比一下 sstr 以及 tstr 
                while(check() && left <= right) {
                    // 长度变化
                    if(len > right-left +1) {
                        // 标记 左边界
                        ans_left = left;
                        len = right - left + 1;    
                    }
                    // 去掉
                    sstr[s[left]]--;
                    // 左边界移动
                    left++;
                }
            }
        }
        if(ans_left == -1) return "";
        else return s.substr(ans_left, len);
    }
};

收获

1. unordered_map 的基本使用
2. 滑动窗口模版
3. auto 基本使用

定义一个字符串的个数哈希表
unordered_map<char, int> sstr, tstr;
简单访问
sstr[s[i]] 这个访问就是对应的个数

int main() {
    unordered_map<char, int> myMap;
    unordered_map<char, int> myMap2;
    myMap['a'] = 1;
    myMap['b'] = 2;
    myMap['c'] = 3;
    
    myMap2['a'] = 3;
    myMap2['b'] = 1;
    myMap2['c'] = 2;


    // 打印 unordered_map 中的元素
    for (auto pair : myMap) {
        cout << pair.first << ": " << pair.second << endl;
        cout<<myMap2[pair.first]<<endl;
        cout<<myMap[pair.first]<<endl;
    }
}