双指针滑动窗口整理1——长度最小的子数组、水果成篮

209. 长度最小的子数组

这篇文章主要是想针对这题 209. 长度最小的子数组，总结一下双指针或是滑动窗口的小细节。对于暴力算法，我们就不再阐释了。

算法原理：

滑动窗口主要是通过控制循环终止节点j，并移动i来缩放窗口。具体而言，当大小为j - i + 1的窗口内所有元素sumnums达到要求sumnums >= target的时候，计算此时的长度是否是达到要求的最小长度 minlen = min(minlen, j - i + 1)。同时，缩小窗口i += 1，继续判断此时的窗口内元素总和的大小。

代码呈现

这里我们使用了两种表示方法，注意观察两者之间的区别。这里我们直接将最小长度minlen赋值为无穷大float('inf')。

方法一：遍历了j，当满足条件sumnums >= target缩小窗口。但是，因为使用了if语句，我们需要把j -= 1,sumnums = sumnums - nums[i] -nums[j]。原因是后面迭代了j += 1且再一次经过条件j < len(nums)时，sumnums += nums[j]。该做法相当于是把缩小后的窗口中总数值是否大于target的判断交给下一次迭代。

方法二：该方法在需要缩小窗口的时候使用了while，即在本次迭代中不断缩小窗口，直到总和小于target，进入下一次迭代。因为停留在本次迭代中（j不变），所以在while循环中不会涉及到j和nums[j]的变化。

两种方法本质上是一样的，只是关于if和while的实现细节容易出错。可以使用target = 5， nums = [1, 1, 1, 1, 4]来作为例子试一试。

第一种

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:minlen = float('inf')sumnums = 0i = 0j=0while j < len(nums):sumnums += nums[j]if sumnums >= target:minlen = min(minlen, j - i + 1)sumnums = sumnums - nums[i] -nums[j]j -= 1i += 1j += 1return minlen if minlen != float('inf') else 0

第二种

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:minlen = float('inf')sumnums = 0i = 0j=0for j in range(len(nums)):sumnums += nums[j]while sumnums >= target:minlen = min(minlen, j - i + 1)sumnums = sumnums - nums[i]i += 1return minlen if minlen != float('inf') else 0

904. 水果成篮

对于双指针方法，我们举一反三。 904. 水果成篮

下面对题目进行文字的数学转化：

1. 题目中“要尽可能多地收集水果”，表示滑动窗口的大小maxnums尽可能大。

2. “只有两个篮子，并且每个篮子只能装单一类型的水果”，表示len(basket) <= 2。每一次通过 if fruits[j] not in basket看看在不在篮子里。因为总量没有限制，在就不管，不在篮子里就加入篮子里。

3. “可以选择任意一棵树开始采摘” 表示滑动窗口左边界i可以随便移动。“每采摘一次，你将会向右移动到下一棵树，并继续采摘。” 表示滑动窗口从左往右移动，是连续的。

注意：
为了方便分析，我们用basket表示篮子里面所装的水果种类，record记录每一种水果种类有多少。为什么要使用record。就是当窗口需要缩小的时候，fruit[i]类型的水果我们不知道在窗口中具体有多少个，所以不能随意地将它pop出篮子。例如，对于fruits = [3,3,3,1,2,1,1,2,3,3,4]，在选中basket = [1, 2, 1, 1 ,2]为滑动窗口的时候（此时fruit[j] = 3），我们需要将i = 3向后挪一位（fruit[i] = 1），但后面还要1种类的水果，所以即使往后移动窗口，篮子里面种类还是不变的。

代码如下：

class Solution:def totalFruit(self, fruits: List[int]) -> int:maxnums = 0i = 0basket = [] # 篮子——basket里面只能有两种数字 len(basket) <= 2 record = {} # 需要记录个数for j in range(len(fruits)):if fruits[j] not in basket:basket.append(fruits[j])record[fruits[j]] = 1else:record[fruits[j]] += 1while len(basket) > 2:maxnums = max(maxnums, j - i)if record[fruits[i]] == 1: basket.pop(basket.index(fruits[i]))record[fruits[i]] = 0else:record[fruits[i]] -= 1i += 1maxnums = max(maxnums, j - i + 1)return maxnums

值得一提的是，record和basket可以合二为一，使得代码更简单，这里就不再赘述了。

后面接着整理：双指针滑动窗口整理2——最小覆盖子串。