3-7节中Minimum Size Subarray Sum滑动窗口解法有个地方有点模糊

Question

3-7节中Minimum Size Subarray Sum中，暴力解法肯定是可以考虑到所有的子数组，但是有点模糊的是，滑动窗口的解法如何保证所有可能的子数组都考虑到呢？因为数组不一定是sorted的，所以有没有可能会漏了一些情况呢？不知道我说清楚了没有，望老师解答！

Answer 1

liuyubobobo 2018-03-09 11:08:06

滑动窗口的思路比暴力求解的思路，节省的时间在于：如果已经知道一个连续子数组的和小于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