560 和为k的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
思路：一次遍历元素，当当前累积和超过k时（若当前元素>k，直接切换到下一元素），去除前置元素至和小于k（用长度length调用前置元素）
class Solution(object): def subarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ summ, length, out = 0, 0, 0 for i, val in enumerate(nums): if val >= k: summ, length = 0, 0 out += 1 if val == k else 0 continue else: summ, length = summ+val, length+1 if summ < k:continue else: while summ > k: length -= 1 summ -= nums[i-length] if summ == k: length -= 1 summ -= nums[i-length] out+=1 return out #这一版代码只适用于数组元素为正的情况...只能通过32/93个案例官方思路：前缀和 sum[i, j] = pre[j]-pre[i-1]=k 由于 i-1<j，所以遍历到下标 j 时就能判断 [0,j] 内有多少满足求和条件的子数组；
class Solution(object): def subarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ tmp = {0:1} summ, out = 0, 0 for i in range(len(nums)): summ += nums[i] out += tmp[summ-k] if summ-k in tmp else 0 tmp[summ] = 1 if summ not in tmp else tmp[summ]+1 #在[0:i-1]内搜索前缀和，再更新[0;j]的前缀和 return out
239 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
官方思路：当窗口右滑 有新元素入窗时，移出所有值小于新元素的元素，再判断现有最大值是否超出窗口长度， 用双向队列来维护当前窗口内元素坐标；
from collections import deque class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ idx = deque() out = [] for i in range(len(nums)): while idx and nums[i] > nums[idx[-1]]: #pop对空队列操作会报错 idx.pop() idx.append(i) # if i == k-1:out.append(nums[idx[0]]) #i=k-1时刚好取完第一个窗口长度，此时需要取一次最大值 if i >= k-1: while idx[0] <= i-k: #当i=k时才会需要判断最大值是否超过窗口 idx.popleft() out.append(nums[idx[0]]) return out
双端队列
1.len(deque)
2.deque.appendleft(val) #将val插入到队头
deque.append(val) #将val插入到队尾
deque.insert(idx, val) #将val放在idx，idx越界时会自动更改到边界位置
deque.extendleft(list) #将list插入到队头 会改变list中元素的相对位置
deque.extend(list) #将list插入到队尾
3.deque.popleft() #移除队头元素
deque.pop() #移除队尾元素，队列为空会报错
4.deque[idx] = val #通过索引更改元素
5.deque.index(val) #查找元素对应的索引，没有匹配会报错
6.deque.count(val) #统计val的数量
7.deque.remove(val) #移除第一个匹配的元素，没有匹配会报错
deque.clear() #清空
8.deque.reverse() #翻转
deque.rotate(k) #循环右移k步（首尾相接）76 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""
官方思路：用双指针维护一个滑动窗口，先增大right指标至窗口内能找到t中的全部字母，然后移动left指标缩小窗口；在即将要破坏满足全部字母的条件时，若此时窗口长度更小，则记录下指针坐标；
class Solution(object): def minWindow(self, s, t): """ :type s: str :type t: str :rtype: str """ if len(s) < len(t):return '' hasht = {} left, right, out = 0, 0, [0, len(s)+1] for i in range(len(t)): #用counter可以直接生成字典 hasht[t[i]] = hasht[t[i]] + 1 if t[i] in hasht else 1 while right < len(s): if s[right] in hasht: hasht[s[right]] = hasht[s[right]] - 1 while max(hasht.values()) == 0 and left <= right: #此时找到所有元素，移动left指针 if s[left] in hasht: hasht[s[left]] = hasht[s[left]] + 1 if right-left<out[1]-out[0]: out[0], out[1] = left, right+1 #切片右侧取不到 left += 1 right += 1 return '' if out[1]>len(s) else s[out[0]:out[1]]优化：max(hasht.values()) == 0 需要每次遍历，可以用needcnt记录欠缺元素的数量；
class Solution(object): def minWindow(self, s, t): """ :type s: str :type t: str :rtype: str """ if len(s) < len(t):return '' left, right, out = 0, 0, [0, len(s)+1] needcnt = len(t) hasht = Counter(t) while right < len(s): if s[right] in hasht: hasht[s[right]] = hasht[s[right]] - 1 if hasht[s[right]] >= 0: needcnt -= 1 #只有hasht[s[i]]为负时才是重复元素 while needcnt == 0 and left <= right: if s[left] in hasht: hasht[s[left]] = hasht[s[left]] + 1 if hasht[s[left]] > 0: needcnt += 1 #只有hasht[s[i]]为正时才是欠缺元素 if right-left<out[1]-out[0]: out[0], out[1] = left, right+1 left += 1 right += 1 return '' if out[1]>len(s) else s[out[0]:out[1]]
