20 天才能结束，才到 12 天啊。

438. Find All Anagrams in a String

Analysis

找出字符串 s 中存在的 p 的字母异位词。

Code

这种题很容易想到 $O(n^2)$ 的暴力解法，但是数据规模是 $[1, 3 × 10^4]$，毫无疑问会超时。按照题目的类型来看，应该是滑动窗口的题目，先把暴力解法写出来吧。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int slen = s.length(), plen = p.length();
        vector<int> cnt(26);
        for(int i = 0; i < plen; i++) {
            cnt[p[i] - 'a']++;
        }
        vector<int> ret;
        for(int i = 0; i <= slen - plen; i++) {
            vector<int> tmp(26);
            for(int j = i; j < i + plen; j++) {
                tmp[s[j] - 'a']++;
            }
            if(tmp == cnt) ret.push_back(i);
        }
        return ret;
    }
};

没想到，这个暴力解法也能过。判断是否是字母异位词也可以用排序来实现，这是从昨天的题中学来的，但是排序的时间复杂度是 $O(nlogn)$，不如 $O(n)$ 的散列来的快。
现在再回头考虑如何用滑动窗口来处理：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int slen = s.length(), plen = p.length();
        if(slen < plen) return {};
        vector<int> ret, cnt(26), tmp(26);
        for(int i = 0; i < plen; i++) {
            cnt[p[i] - 'a']++;
            tmp[s[i] - 'a']++;
        }
        if(cnt == tmp) ret.push_back(0);
        for(int i = 0; i < slen - plen; i++) {
            tmp[s[i]- 'a']--;
            tmp[s[i + plen] - 'a']++;
            if(tmp == cnt) ret.push_back(i + 1);
        }
        return ret;
    }
};

滑动窗口的难点在于如何理解窗口，就这个题来讲，窗口的大小就是字符串 p 的长度。每次滑动窗口的时候，就把左端的字符从窗口移出去，再把右端的字符加入到窗口中来。
官方题解还提供了一种优化版的滑动窗口思路，即不再统计窗口内字符的数量，只用一个变量 diff 来记录当前窗口字符串与 p 中数量不同的字母的个数。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int slen = s.length(), plen = p.length();
        if(slen < plen) return {};
        vector<int> ret, cnt(26);
        for(int i = 0; i < plen; i++) {
            cnt[s[i] - 'a']++;
            cnt[p[i] - 'a']--;
        }
        int diff = 0;
        for(int i = 0; i < 26; i++) {
            if(cnt[i] != 0) diff++;
        }
        if(diff == 0) ret.push_back(0);
        for(int i = 0; i < slen - plen; i++) {
            // left 
            if(cnt[s[i] - 'a'] == 1) diff--;
            else if(cnt[s[i] - 'a'] == 0) diff++;
            cnt[s[i] - 'a']--;
            // right
            if(cnt[s[i + plen] - 'a'] == -1) diff--;
            else if(cnt[s[i + plen] - 'a'] == 0) diff++;
            cnt[s[i + plen] - 'a']++;
            // judge
            if(diff == 0) ret.push_back(i + 1);
        }
        return ret;
    }
};

注意下标为 0 时的判断得写在外面，目的是为了在滑动窗口的循环中先滑动窗口，再进行判断，这样就可以取到下标为 slen - plen 的位置了，且不至于越界。
翻了下评论区，好像还有一种滑动窗口的解法：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int slen = s.length(), plen = p.length();
        if(slen < plen) return {};
        vector<int> ret, cnt(26);
        for(int i = 0; i < plen; i++) {
            cnt[p[i] - 'a']++;
        }
        int left = 0, right = 0;
        while(right < slen) {
            cnt[s[right] - 'a']--;
            while(cnt[s[right] - 'a'] < 0) {
                cnt[s[left] - 'a']++;
                left++;
            }
            if(right - left + 1 == plen) ret.push_back(left);
            right++;
        }
        return ret;
    }
};

感觉这种解法不太好想，最好想的解法还是一开始的滑动窗口解法。滑动窗口的解法，应该是从双指针衍生出来的解法。难点在于，如何移动窗口的左端点 left，并同时将符合条件的解找出来。回到上面的解法来，巧妙之处在于在移动 left 的同时，让统计（也可以叫 hash）数组 cnt 还原了。

713. Subarray Product Less Than K

Analysis

找出乘积小于 k 且元素连续的子数组，这个题一看也是滑动窗口的题，也是 5 月 5 日的每日一题。

Code

暴力解法死在 93 个用例了😂。

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k == 0) return 0;
        int size = nums.size(), cnt = 0;
        for(int i = 0; i < size; i++) {
            int product = 1;
            for(int j = i; j < size; j++) {
                product *= nums[j];
                if(product < k) cnt++;
                else break;
            }
        }
        return cnt;
    }
};

直接换滑动窗口：

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k == 0) return 0;
        int size = nums.size(), cnt = 0;
        int left = 0, right = 0, product = 1;
        while(right < size) {
            product *= nums[right];
            while(left <= right && product >= k) {
                product /= nums[left];
                left++;
            }
            cnt += right - left + 1;
            right++;
        }
        return cnt;
    }
};

这里的难点在于理解子数组个数 cnt 的计算，这个值是随着滑动窗口的改变而改变的，每一次循环，加入或者减少元素，这个值都需要加上当前窗口内元素能构成的子数组个数。也就是说，当前窗口 $[left, right]$ 能构成的符合条件的子数组个数就是 $right - left + 1$ 个，把所有窗口的情况全加起来就是要求的结果了（这也是处理这类连续问题的关键）。
官方题解还提供了一种有趣的可以用二分来解决的方法：

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k == 0) return 0;
        int size = nums.size();
        vector<double> logprefix(size + 1);
        for(int i = 0; i < size; i++) {
            logprefix[i + 1] = logprefix[i] + log(nums[i]);
        }
        double logk = log(k);
        int cnt = 0;
        for(int r = 0; r < size; r++) {
            int l = upper_bound(logprefix.begin(), logprefix.begin() + r + 1, logprefix[r + 1] - logk + 1e-10) - logprefix.begin();
            cnt += r + 1 - l;
        }
        return cnt;
    }
};

这种方法需要用到前缀和、二分查找和数学知识，很灵活，不是那么好想。

Summary

滑动窗口掌握的还不熟练，还得再来点题目才行。