滑动窗口

插个眼

以后写

先做题…

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

解：

滑动窗口

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> last(256, -1);   // 记录每个字符上一次出现的位置
        int ans = 0,left = 0;        // 窗口左边界
        for(int right = 0; right < s.size(); right++){
            if(last[s[right]] >= left){
                left = last[s[right]] + 1;  // 如果字符在当前窗口中重复，移动左边界
            }
            last[s[right]] = right;
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

438.找到字符串中所有字母异位词

解：

同理

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        if(s.size() < p.size()) return res;

        vector<int> cnt(26,0);

        // 统计 p 中每个字母需要多少个
        for(char c: p){
            cnt[c - 'a']++;
        }

        int left = 0, right = 0;
        int need = p.size();  // 还需要匹配的字符个数

        while(right < s.size()){
            // 扩展右边界
            if(cnt[s[right] - 'a'] > 0){
                need--;
            }
            cnt[s[right] - 'a']--;
            right++;

            // 当窗口大小等于 p 的长度时，开始判断并移动左边界
            if(right - left == p.size()){
                if(need == 0){
                    res.push_back(left);
                }

                // 收缩左边界
                if(cnt[s[left] - 'a'] >= 0){
                    need++;
                }
                cnt[s[left] - 'a']++;
                left++;
            }
        }
        return res;
    }
};