算法第六天 滑动窗口

完成日期：7月14日，7月16日
今日总结：

1. 滑动窗口，借助双指针
2. 它们的区别：
   滑动窗口：固定两个指针的间距，向右滑动
   双指针：两个快慢指针，间距动态变化，向右滑动
3. 判断有无重复元素，可用unorder_set无序集合，需要熟悉STL用法和它们的方法

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

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

// 滑动窗口双指针
int lengthOfLongestSubstring(string s) {
        int left=0, right=1, len=s.length();
        if(len<2) return len;
        int max=1;
        unordered_set<char> myset;
        myset.insert(s[left]);
        while(right<len){  
            if(myset.find(s[right]) != myset.end()){  //记住这种方法，下次也试试用count()
                myset.erase(s[left++]);
            }
            else{
                myset.insert(s[right++]);
                max = right-left>max?right-left:max;
            }
        }
        return max;
    }

567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

// 方法一：滑动窗口
// 这思路有点绕，使用了diff记录是否满足题目
bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        if(n>m) return false;
        vector<int> cnt(26);
        for(int i = 0; i<n; ++i){
            --cnt[s1[i] - 'a'];
            ++cnt[s2[i] - 'a'];
        }
        int diff = 0;
        for(int c:cnt){
            if(c!=0){
                ++diff;
            }
        }
        if(diff == 0){
            return true;
        }
        for(int i=n; i<m; ++i){
            int x= s2[i]-'a', y =s2[i-n]-'a';
            if(x==y) continue;
            if(cnt[x]==0) ++diff;
            ++cnt[x];
            if(cnt[x]==0) --diff;
            if(cnt[y]==0) ++diff;
            --cnt[y];
            if(cnt[y]==0)  --diff;
            if(diff == 0) return true;
        }
        return false;
    }

// 方法二：双指针
bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        if(n>m) return false;
        vector<int> cnt(26);
        for(int i = 0; i < n; ++i){
            --cnt[s1[i]-'a'];
        }
        int left = 0;
        for(int right=0; right < m; ++right){
            int x=s2[right]-'a';
            ++cnt[x];
            while(cnt[x]>0){
                --cnt[s2[left]-'a'];
                ++left;
            }
            if(right-left+1==n){
                return true;
            }  
        }
        return false;
    }