窗口类双指针

用法： 什么时候可以使用Window类双指针解法

• 题目求的是最长／最短的subarray/substring。因为Window类双指针优化的是暴力解已经 是O(n^2)的问题，而求subrray/substring的话，暴力解就是O(n^2), 因为只需要遍历起点和终点

• 其次可以通过观察O(n^2)的暴力解有没有重复遍历的问题来验证是否可以用双指针。比如去找到 一个刚刚满足题目条件的解，观察在这个window range里面是否会有其他解，如果没有，说明 我们可以用双指针优化

• 如果是subarray sum的问题，那么integer必须得是正数。因为这样才能保证在同一段区间内，长区间比短区间的sum大。如果题目可以有negatives，那么多半这道题是subarray sum equals k的类型而非窗口类双指针问题。

步骤：Window类双指针解法4要素

可以先来看一下window类双指针的模版

  (0). 决定start和end哪一个为慢指针,也就是决定到底是整多了的问题还是还不够的问题，一般来说，如果是求minLen的问题，那么一般是还不够，如果是求maxLen的问题，那么一般是整多了。这里可以反过来想。
  for (慢指针循环) {
    (1). while (window不满足题意 && index没有out of bound) {
        update快指针使它逐渐接近满足题目要求
    }
    //一旦刚刚满足条件就break out of while loop, 因为现在我们已经可能有一个
    //可行解了，并且start和and之前都是多余情况不用扫描了（因为我们是在刚刚满足条件
    //的时候才break，换言之就是window之内的都不满足）这里需要if condition去check一下
    //是因为我们可能是因为index才break的，这种情况的window是不满足条件的
    (2). if (满足条件) {
        和全局解比较一下
    }
    (3). 考虑慢指针的影响，如果慢指针是start，那么要消除掉start指针的影响，如果慢指针是end，那么要加入end的影响
}

(4). return ...前别忘了补刀，因为有可能根本没有可行解。所以要check result是不是我们
之前设置的特殊值

(0).决定start和end哪一个作为慢指针。这有两种情况：

• 还不够：e.g. minimum window substring/minimum size subarray, 这两道题的限制条件 都是使得我们的window至少得有某一个size，所以我们得不断扩大窗口使之满足条件。所以我们 的对策是选择start作为慢指针，而让end作为快指针可以尽可能多的扩大窗口。

• 整多了：e.g. longest系列。这种题目的限定条件都是在压制窗口的size。所以我们得不断缩小 窗口来满足条件。所以我们的对策是选择end作为慢指针，而让start作为快指针尽可能的缩小窗口。

(1). 这里头最关键的算法部分就是弄清楚什么是不满足条件的情况，并把它填到while loop的条件里面 并且在while loop里面移动快指针使window逼近合法解. 比如说对于min sized subarray sum, 不满足条件 就是sum <= target; 对于longest substring wiht at most k distinct chars， 不满足条件就是 map.size() > k; 对于min window substring，不满足条件就是str还没有包含所有target's chars; 对于 longest substring without repeating chars，不满足条件就是有chars的count >= 2

(2) 一旦跳出了while loop，说明我们可能有一个合法解了。说有可能，是因为while loop 可能是因为index的问题才被break。不过进了if condition说明我们有一个合法解了，可以和全局 的解进行比较。这个window对于理解双指针算法非常重要。因为通过我们的算法，这个window内部 的小窗口都是不满足题意的，所以没有重复遍历的必要，这解释了为什么我们永远都是同向前进 指针而不用回退。

(3). 我们不要忘了考虑慢指针的影响。

(4). 最后记得补刀，因为可能没有合法解。

题目

整多了

• Leetcode 340. Longest Substring with At Most K Distinct Characters (Facebook店面)
• Leetcode 159. Longest Substring with At Most Two Distinct Characters
• Leetcode 3. Longest Substring Without Repeating Characters

还不够

• Leetcode 209. Minimum Size Subarray Sum
• Leetcode 76. Minimum Window Substring