滑动窗口用法

1. 长度最小的子数组（模板）

1. 题目分析

直接用步骤分析示例1，[]表示窗口，min_length表示满足条件的最短子数组，sum表示窗口内元素的总值：- [2],3,1,2,4,3		min_length=100001，sum=2 < target=7- [2,3],1,2,4,3		min_length=100001，sum=5 < target=7- [2,3,1],2,4,3		min_length=100001，sum=6 < target=7- [2,3,1,2],4,3		min_length=4，     sum=8 >= target=7- PS：只要sum>=target，就尝试将左窗口向右移动，若仍满足条件，就更新min_length，不行就继续- [2,3,1,2,4],3		min_length=5，	  sum=12 >= target=7- 2,[3,1,2,4],3		min_length=4，	  sum=10 >= target=7- 2,3,[1,2,4],3		min_length=3，	  sum=7 >= target=7- 2,3,[1,2,4,3]		min_length=4，	  sum=10 >= target=7- 2,3,1,[2,4,3]		min_length=3，	  sum=9 >= target=7- 2,3,1,2,[4,3]		min_length=2，	  sum=7 >= target=7- 最后返回min_length=2

2. 代码实现

def minSubArrayLen(target, nums):""":type target: int:type nums: List[int]:rtype: int"""n = len(nums)# l表示左窗口的位置，r表示右窗口的位置l = r = 0# sum表示窗口内的元素总值sum = nums[0]# 如果第一个元素的值就大于等于target，直接返回if sum >= target:   return 1# 设置成100001是因为测试用例的数组长度最长为100000min_length = 100001# 循环n - 1次for i in range(1, n):# 右窗口肯定是要一直移动的，不存在每次循环不移动的情况r += 1sum += nums[r]# 如果sum去掉靠近左窗口的那个元素后仍然大于sum，就该减小窗口的长度了while sum - nums[l] >= target:sum -= nums[l]l += 1# 经过上述步骤后，当来到右窗口此时的位置时，满足条件的窗口长度就得到了if sum >= target:min_length = min(min_length, r - l + 1)# 数组所有元素的总和加起来都小于target，min_length就返回0return 0 if min_length == 100001 else min_length

3. 精简版

def minSubArrayLen(target, nums):""":type target: int:type nums: List[int]:rtype: int"""n = len(nums)l = r = 0min_length = 100001sum = 0while r < n:sum += nums[r]while sum - nums[l] >= target:sum -= nums[l]l += 1if sum >= target:min_length = min(min_length, r - l + 1)r += 1return 0 if min_length == 100001 else min_length

2. 无重复字符的最长字串

注意s字符串包含：字母、数字、符号和空格

1. 题目分析：

以abcabcbb为例，max_length表示最长无重复字串字串，l表示左窗口，r表示右窗口：- [a]bcabcbb		max_length=1- [ab]cabcbb		max_length=2- [abc]abcbb		max_length=3- [abca]bcbb- 下面这一步就很重要了，l=max(l,a上一次出现位置+1)- a[bca]bcbb		max_length=3- a[bcab]cbb		l=max(l,b上一次出现位置+1)- ab[cab]cbb		max_length=3- ab[cabc]bb		l=max(l,c上一次出现位置+1)- abc[abc]bb		max_length=3- abc[abcb]b		l=max(l,b上一次出现位置+1)- abcab[cb]b		max_length=3- abcab[cbb]		l=max(l,b上一次出现位置+1)- abcabcb[b]		max_length=3

2. 代码实现

def lengthOfLongestSubstring(s):""":type s: str:rtype: int"""n = len(s)# 字母、数字、空格和一些符号的ascii码都在0~255之间pos = [-1] * 255l = 0max_length = 0for r in range(n):# 在r移动到下一个字符位置时，一定要先让l获取上次这个字符出现的位置并且加1l = max(l, pos[ord(s[r])] + 1)# 然后再更新这个字符出现的位置pos[ord(s[r])] = r# 最后通过比较获得wu'cmax_length = max(max_length, r - l + 1)return max_length

3. 最小覆盖字串

1. 题目分析

1. 拿一个cnts数组统计t串中字符的出现次数，total记录t中每个字符出现次数的总和
2. 首先，t中字符每出现一次，cnts[ord(t[i])] -= 1
3. 然后开始循环s字符串
4. 如果遇到出现次数小于0的，total就减-1
5. 每循环一次，该字符的出现次数就加1（我们只关注t中的字符，s中其它字符正常加就行了，后面不会涉及到它们）
6. 当total == 0时，也就是说当前窗口中已经包含了t中所有字符
7. 开始判断，左窗口所指向的字符出现次数是否大于0，大于0左窗口就可以向右移动了
8. PS：当total第一次等于0时，表示窗口中恰好有t中每个字符，且它们的出现次数都为0，后续可能会有多余的，它们的出现次数就会大于0，s中其它字符最开始都是0，只要在窗口中，它们的出现次数就会大于0
9. 然后判断当前窗口的长度跟最小覆盖字串的长度比较，取较小的那个cnts是统计所有字符的出现次数，初始化为0- 首先是将t串中每个字符的出现次数减1，也就是说，除了t串中的字符出现次数是负数，其它字符的出现次数都是0- 然后就是只要有一个字符进窗口，出现次数加1- 当左窗口字符出现次数大于0时，就可以考虑将其删除了

2. 代码实现

def minWindow(s, t):""":type s: str:type t: str:rtype: str"""n = len(s)m = len(t)# 如果s串长度小于m长度，s就不可能有长度大于等于m的字串if n < m:return ""total = m# 计数数组cnts = [0] * 255# 给t串中每种字符出现次数为负数for i in range(m):cnts[ord(t[i])] -= 1l = 0target = ''min_length = 100001# 开始遍历s串for r in range(n):# 能满足下面if语句条件的一定是t串中的字符if cnts[ord(s[r])] < 0:total -= 1# 不管是哪个串中的字符，次数都要加1cnts[ord(s[r])] += 1# total==0表示窗口中已经包含了t串所有字符if total == 0:# 开始判断左窗口可不可以移动while cnts[ord(s[l])] > 0:cnts[ord(s[l])] -= 1l += 1# 取最小覆盖字串的长度if r - l + 1 < min_length:min_length = r - l + 1target = s[l : r + 1]return target

4. 加油站

1. 题目分析

用左窗口遍历一遍加油站即可，此时左窗口就相当于起点，右窗口就从左窗口开始向后遍历，只要出现油不够的情况，左窗口就向右移动。可以将gas和cost数组合并来看，例如：
gas 	= [1,2,3,4,5]
cost	= [3,4,5,1,2]
combine = [-2,-2,-2,3,3]
combine[0]表示从第0个加油站开到第1个加油站倒欠2升油，所以无法以第0个加油站为起点，开到第一个加油站
combine[3]表示从第4个加油站开到第5个加油站多出了3升油，所以能以第4个加油站为起点，开到第五个加油站

2. 代码

def canCompleteCircuit(gas, cost):""":type gas: List[int]:type cost: List[int]:rtype: int"""n = len(gas)# sum表示路上的总油量，只要油量小于0了，就不能走sum = 0# len表示一共走了几个加油站length = 0for l in range(n):while sum >= 0:# 如果从某个加油站出发，能走完一圈，就返回那个加油站的位置if length == n:return lr = (l + length) % nlength += 1sum += gas[r] - cost[r]# 走到这说明sum<0了，那么左窗口就该移动了，且sum要减去左窗口移动之前所在位置的那个值，len也要减1sum -= gas[l] - cost[l]length -= 1# 如果以每个加油站为起点出发，sum最后都会小于0，就返回-1return -1

5. 替换字串得到平衡字符串

1. 题目分析

思路：
1. 先统计每种字符的出现次数
2. 然后用窗口框柱一段字符，假设窗口外的每种字符出现次数不等于 n/4，判断只替换窗口内的字符能否使窗口外的每种字符字符出现次数都变成n/4
3. 如果该窗口不行，那么它的子窗口一定不行（这里没想出为什么）如果[l,r-1]不行，[l,r]行，那么[l+1,r]也有可能行，[l+1,r-1]就一定不行4. 那么怎么实现第二步？假如窗口长度为8，窗口外面字符出现次数为Q->18,W->19,E->16,R->19，要求是每种字符出现20次8-(20-18) = 66-(20-19) = 55-(20-16) = 11-(20-19) = 0最后剩余0，表示能行如果外面某种字符超过了平均出现次数，那么这个窗口一定不行

2. 代码实现

def balancedString(s):""":type s: str:rtype: int"""# 这个函数就是实现上面分析的第四步# len表示窗口的大小，也就是有len个元素可以替换，看能不能使窗口外面的每种字符出现次数达到averdef ok(cnts, len, aver):for i in range(4):if cnts[i] > aver:return Falselen -= aver - cnts[i]return True if len == 0 else Falsen = len(s)aver = n // 4# 将Q映射成0，W映射成1，E映射成2，R映射成3data = ['Q', 'W', 'E', 'R']cnts = [0] * 4for i in range(n):cnts[data.index(s[i])] += 1# 作为替换字串的最小长度返回ans = nr = 0# 左窗口开始遍历sfor l in range(n):# l-r表示[l,r)范围# 如果当前窗口不行，右窗口jiwhile ok(cnts, r - l, aver) == False and r < n:# 右窗口每次向右移动都会在窗口内新加入一个字符，它在窗口外的出现次数要减1cnts[data.index(s[r])] -= 1r += 1# 这里是为了判断上面循环是因为第一个条件结束还是因为第二个条件结束的# 若是因为第二个条件结束的，就说明这个窗口是合法的，当然这里只能判断第一个条件# 因为第一个条件也有可能不符合if r != n:ans = min(ans, r - l)# 最后一次循环结束后，左窗口会向右移动，相当于会将它原来所在位置的字符排除到窗口外，所以在窗口外这个字符的出现次数要加1cnts[data.index(s[l])] += 1return ans