2020年5月上旬【算法讨论】滑动窗口

[yudidi]

209. 长度最小的子数组
关于滑动窗口会不会漏掉解的分析// 参考附录1
3. 无重复字符的最长子串
配套练习
438. Find All Anagrams in a String
https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/
76. 最小覆盖子串 && 76. Minimum Window Substring
567. 字符串的排列

1. https://www.cnblogs.com/yudidi/p/12772573.html
2. https://www.cnblogs.com/yudidi/p/12774460.html

滑动窗口的编码框架
滑动窗口的编码框架-英文版

[yudidi]

主要内容简记

开发软技能

单体架构和微服务
技术选型(关注缺点)
良好的开发流程

接下来1年左右的学习内容

1. 算法 2. 性能优化 3. gin框架学习和架构设计

滑动窗口题目-速记

寻找满足某种条件的连续子串或连续子数组的题目,就可以用滑动窗口的思路

海哥的小优化-> 3. 无重复字符的最长子串

res = max(res,r-l+1);最后比较最大无重复子串的长度这一步，只需要在 r 向右移动过程中进行比较就行了。l 向右移动时可以不用比较。代码改为：`int lengthOfLongestSubstring(string& s){
int freq[256] = {0};
int l = 0, r = -1;
int res = 0;

while (l < s.size()) {
    if (r + 1 < s.size() && freq[s[r+1]] == 0) {
        freq[s[++r]]++;
        // 只在滑动窗口右端向右移动时比较。
        res = max(res, r-l+1);
    } else {
        freq[s[l++]] --;
    }
}
return  res;

https://coding.imooc.com/learn/questiondetail/108429.html

[yudidi]

滑动窗口的思路比暴力求解的思路，节省的时间在于：如果已经知道一个连续子数组的和小于sum了，就不需要再去检查这个连续子数组中的其他子数组了；同理，如果已经知道一个连续子数组的和大于sum了，就不需要再去检查在这个连续子数组的基础上添加新元素的连续子数组了。

上述这个回答其实并没有回答你的问题，只是首先希望你能感性的想明白：�滑动窗口的思路为什么是work的，暴力求解的思路的冗余点在哪里。如果还不很理解，可以用这个题目的测试用例感受一下：对于[2,3,1,2,4,3] and s = 7这个输入，暴力求解需要检查哪些子数组；而滑动窗口需要检查哪些子数组，比起暴力求解少检查了哪些情况，为什么可以少检查这些情况。

大多数同学如果对上述问题已经很清晰了的话，对于滑动窗口结果的正确性的顾虑应该打消了。或者你可以这样思考这个问题：滑动窗口算法没有考虑的情况只有两类：

1）已知一个子数组subarr的和 < sum，这个子数组subarr中的所有连续子数组

2）已知一个子数组subarr的和 > sum，包含这个子数组subarr的所有更大的连续子数组

显然，一个问题的解是不可能蕴含在这两种情况中的，所以我们的算法不会漏掉正确的解。

但是，很遗憾，其实上述描述并没有完全严谨的证明这个算法的正确性。完全严谨的证明有些复杂，它本质和证明贪心选择性质一样（印象里我在这个课程的贪心部分会讲）。通常来讲，一个贪心算法是容易设计且容易编写的，但是，证明贪心算法的正确性是很困难的。这也是贪心算法的难点。如果你上过我的《数据结构与算法》课程的话，可以回想一下最小生成树的Kruskal算法。这个算法过程是很容易描述的，但是为什么这样做就能得到最小生成树？证明起来有一定难度。对于这个问题，我在一个知乎问答上也描述过：

刷题时，遇见过哪些巧妙的贪心算法的题目？ - 刘宇波的回答 - 知乎 https://www.zhihu.com/question/64862744/answer/234821189

通常，对这类问题，如果要严格证明，需要使用反证法。即假设存在一组解，使用我们的算法是找不到的，进而求出矛盾。这个证明过程相对比较冗长。在这个课程中，我曾经在一个问答里证明过另外一个“对撞指针”的问题的正确性（对撞指针也可以看做是一个窗口，只不过这个窗口在逐渐缩小。同时，这个问题也是一个很经典的leetcode上的问题：11号问题）。有兴趣可以看一看，看看是否能够帮助你严谨的证明出在这个问算法的正确性，如果你感兴趣的话：）

https://coding.imooc.com/learn/questiondetail/19327.html

[yudidi]

欢迎来找bug

https://leetcode-cn.com/problems/minimum-window-substring/

func minWindow(s string, t string) string {
    window,need,match := make(map[rune]int),make(map[rune]int),0
    runes := []rune(s)
    min := append(runes,rune(1))
    for _,v :=range t{
        need[v]++
    }
    l,r:=0,0 // [l,r)
    for r < len(runes) {
        v := runes[r]
        r++
        if times,ok:=need[v];ok{
            window[v]++
            if window[v] == times{
                match++
            }
        }
        for match == len(need) {
            if r-l < len(min){
                min = runes[l:r]
            }
            d := runes[l]
            l++
            if _,ok := need[d];ok{
                match--
                window[d]--
            }
        }
    }
    if len(min) == len(runes) + 1{
        return ""
    }
    return string(min)
}