滑动窗口

Leetcode Hot100第三个小专题，两道题，于我而言，滑动窗口是一种特殊的双指针。传统意义上的双指针，两个指针的位置可以使区间对向或者同向的放大缩小，而滑动窗口的两个指针则一般只是同向的放大缩小。

无重复字符的最长子串

力扣题目连接：无重复字符的最长子串

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

class Solution {
public:
   int lengthOfLongestSubstring(string s) {
       unordered_set<char> sets; 
       //用无序集合来存是为了使用count函数来确认里面有没有重复的字符，也可以用sets.find(...)!=sets.end()来确认
       int i = 0;
       int res = 0;
       for (int j = 0; j < s.size(); j++) {
           while (i < j && sets.count(s[j]) != 0) {//可能先写插入再写判断有没有重复字符再删除比较符合我们理解，但是实际上，无论有没有重复字符，我们都是要将最新的这个字符插入到窗口里面的，在此之前先删除也是没有问题的
               sets.erase(s[i++]);//注意这里使用的是i++，也就是先用i进行操作，然后i自增1
           }
           sets.insert(s[j]);
           res = max(res, j - i + 1);
       }
       return res;
   }
};

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

力扣题目连接：找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

自己写的代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(s.size()<p.size()) return {};
        int left=0;
        int n = p.size();
        sort(p.begin(),p.end());
        vector<int> result;
        for(left;left<s.size()-n+1;left++){  //固定一个字符串p长度相同的窗口，从左向右遍历然后排序后比较，这个算法的时间复杂度为O(n)，很遗憾没有完全AC，题解用了数组来存了二十六个字母单词，降低了时间复杂度，明天再看看详解
            string current = s.substr(left,n);
            sort(current.begin(),current.end());
            if(current == p){
                result.push_back(left);

            }
        }
        return result;
    }
};