滑动窗口经典问题整理
经典
1、无重复字符的最长子串
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:m = defaultdict(int)maxl, j = 0, 0for i, c in enumerate(s):m[c] += 1while j <= i and m[c] > 1:m[s[j]] -= 1j += 1if i - j + 1 > maxl:maxl = i - j + 1 return maxl2、包含所有三种字符的子字符串数目
class Solution:def numberOfSubstrings(self, s: str) -> int:m = defaultdict(int)j, n = 0, len(s)res = 0for i, c in enumerate(s):m[c] += 1while m['a'] >= 1 and m['b'] >= 1 and m['c'] >= 1:res += n - im[s[j]] -= 1j += 1return res3、最长优雅子数组
class Solution:def longestNiceSubarray(self, nums: List[int]) -> int:j, s, n = 0, 0, len(nums)maxl = 1for i in range(len(nums)):while i >= j:if (nums[i] & s) == 0:s |= nums[i]breaks ^= nums[j]j += 1maxl = max(maxl, i - j + 1)return maxl4、K 个不同整数的子数组
转换成为求解「最多存在 K 个不同整数的子区间的个数」与 「最多存在 K−1 个不同整数的子区间的个数」
class Solution:def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:def slidingwindow(k):m, j = {}, 0res = 0for i, num in enumerate(nums):if num not in m:m[num] = 0m[num] += 1while j <= i and len(m) > k:m[nums[j]] -= 1if m[nums[j]] == 0:del m[nums[j]]j += 1res += i - j + 1return resreturn slidingwindow(k) - slidingwindow(k - 1)5、倒序缩小 -- 最小窗口子序列
class Solution:def minWindow(self, s1: str, s2: str) -> str:n = len(s1)minl = "9" * (n + 1)i, k = 0, 0while i < n:if s1[i] == s2[k]:k += 1if k == len(s2):left, p = i, len(s2) - 1while p >= 0:if s2[p] == s1[left]:p -= 1left -= 1left += 1if len(s1[left: i + 1]) < len(minl):minl = s1[left:i + 1]i, k = left, 0i += 1return minl if minl != "9" * (n + 1) else ""6、使数组连续的最少操作数
class Solution:def minOperations(self, nums: List[int]) -> int:n = len(nums)nums = sorted(set(nums))j, minl = 0, inffor i, num in enumerate(nums):while j <= i and num - nums[j] + 1 > n:j += 1minl = min(minl, n - (i - j + 1))return minl7、无限数组的最短子数组 -- （乘二倍，解决循环问题，类似于可见点的最大数目）
class Solution:def minSizeSubarray(self, nums: List[int], target: int) -> int:j, s = 0, 0sum_nums = sum(nums)double_nums = nums * 2minl = inffor i, num in enumerate(double_nums):s = s + numwhile i >= j and s > target % sum_nums:s = s - double_nums[j]j += 1if s == target % sum_nums: minl = min(minl, i - j + 1 + len(nums) * (target // sum_nums))return minl if minl < inf else -18、滑动窗口 + 中位数贪心（通过首尾配对证明） （执行操作使频率分数最大）
class Solution:def maxFrequencyScore(self, nums: List[int], k: int) -> int:nums.sort()pre = [0]for num in nums:pre.append(pre[-1] + num)def get_cost(i, j):s = i - j + 1mid = nums[(i + j) // 2]idx = bisect_right(nums, mid)right = (pre[i + 1] - pre[idx]) - mid * (i + 1 - idx)left = mid * (idx - j) - (pre[idx] - pre[j])return left + right j, maxl = 0, 0for i, num in enumerate(nums):while get_cost(i, j) > k:j += 1maxl = max(maxl, i - j + 1)return maxl9、统计最大元素出现至少 K 次的子数组
class Solution:def countSubarrays(self, nums: List[int], k: int) -> int:mx = max(nums)ans = cnt_mx = left = 0for x in nums:if x == mx:cnt_mx += 1while cnt_mx == k:if nums[left] == mx:cnt_mx -= 1left += 1ans += leftreturn ans注：如果元素存在负数时，窗口的滑动就没有单向性了，所以不适用滑动窗口了，例如和至少为 K 的最短子数组，最佳做法时利用前缀和 + 单调队列，代码如下：
class Solution:def shortestSubarray(self, nums: List[int], k: int) -> int:preSumArr = [0]res = len(nums) + 1for num in nums:preSumArr.append(preSumArr[-1] + num)q = deque()for i, curSum in enumerate(preSumArr):while q and curSum - preSumArr[q[0]] >= k:res = min(res, i - q.popleft())while q and preSumArr[q[-1]] >= curSum:q.pop()q.append(i)return res if res < len(nums) + 1 else -110、子数组按位与值为 K 的数目
当子数组的右侧端点固定时，当左侧端点向左移动时函数值不变或减少，当左侧端点向右移动时函数值不变或增加。当左侧端点向左移动时，函数值的二进制表示的每一位只可能不变或从 1 变成 0，不可能从 0 变成 1，因此当子数组的右侧端点 r 固定时，不同的函数值个数不超过 O(lognums[r])，所以可以采用二分法确定子数组为K的左侧端点的起始点和终止点
由于元素值只会减少，所以当 i 增大时，左侧端点的起始点和终止点位置不会向变大的方向移动，有了单调性的保证，所以可以使用滑动窗口，代码如下：
class Solution:def countSubarrays(self, nums: List[int], k: int) -> int:ans = left = right = 0for i, x in enumerate(nums):for j in range(i - 1, -1, -1):if nums[j] & x == nums[j]:breaknums[j] &= xwhile left <= i and nums[left] < k:left += 1while right <= i and nums[right] <= k:right += 1ans += right - leftreturn ans滑动窗口与有序列表结合
1、存在重复元素 III
class Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:from sortedcontainers import SortedList n = len(nums)s = SortedList()for i, num in enumerate(nums):idx = s.bisect_left(num - valueDiff) if idx < len(s) and s[idx] <= num + valueDiff:return Trues.add(num)if i >= indexDiff: s.remove(nums[i - indexDiff])return False该方法还可以用桶排序的方法去做：
class Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:m, size = {}, t + 1getID = lambda num: num // sizefor i, num in enumerate(nums):nid = getID(num)if nid in m: return Trueif (nid - 1) in m and m[nid - 1] + t >= num: return Trueif (nid + 1) in m and m[nid + 1] - t <= num: return Truem[nid] = numif i >= k: del m[getID(nums[i - k])]return False滑动窗口与单调队列结合
1、预算内的最多机器人数目
class Solution:def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:ans = s = left = 0q = deque()# 枚举区间右端点 right，计算区间左端点 left 的最小值for right, (t, c) in enumerate(zip(chargeTimes, runningCosts)):# 及时清除队列中的无用数据，保证队列的单调性while q and t >= chargeTimes[q[-1]]:q.pop()q.append(right)s += c# 如果左端点 left 不满足要求，就不断右移 leftwhile q and chargeTimes[q[0]] + (right - left + 1) * s > budget:# 及时清除队列中的无用数据，保证队列的单调性if q[0] == left:q.popleft()s -= runningCosts[left]left += 1ans = max(ans, right - left + 1)return ans哈希值 + 滑动窗口 （Rabin-Karp + 二分搜索）
1、最长重复子串
class Solution:def longestDupSubstring(self, s: str) -> str:mod = 10 ** 9 + 7def check(m):t = 0for i in range(m):t = (t * 26 + ord(s[i]) - ord('a')) % modst = set([t])for i in range(m, len(s)):t = (t * 26 + ord(s[i]) - ord('a') - pow(26, m, mod) * (ord(s[i - m]) - ord('a'))) % modif t in st: tt = s[i - m + 1: i + 1]if s.find(tt) != i - m + 1: return True, ttst.add(t)return False, ""l, r = 0, len(s)res = ""while l < r:mid = (l + r) // 2flag, true_s = check(mid)if flag:l = mid + 1res = true_selse:r = midreturn res该题还可以用后缀数组去完成
from array import arrayL_TYPE = ord('L')
S_TYPE = ord('S')def is_lms(i, t):"""Returns whether the suffix/ character at index i is a leftmost S-type"""return t[i] == S_TYPE and t[i - 1] == L_TYPEdef print_types(data: bytearray):"""Simple method to the types of the characters of T"""print(data.decode('ascii'))print("".join("^" if is_lms(i, data) else " "for i in range(len(data))))def classify(text, n) -> bytearray:"""Classifies the suffixes in text as either S-type, or L-typeThis method can be merged with find_lms_suffixes but I have not done so for readabilityArgs:text: the input string/array to be classifiedn: the length of textReturns:t: a bytearray object, where t[i] contains the type of text[i]"""t = bytearray(n)t[-1] = S_TYPEfor i in range(n - 2, -1, -1):if text[i] == text[i + 1]:t[i] = t[i + 1]else:if text[i] > text[i + 1]:t[i] = L_TYPEelse:t[i] = S_TYPEreturn tdef find_lms_suffixes(t, n):"""Finds the positions of all lms_suffixesArgs:t: the type arrayn: the length of text and t"""pos = array('l')for i in range(n):if t[i] == S_TYPE and t[i - 1] == L_TYPE:pos.append(i)return posdef print_buckets(bucks):"""Simple method to print bucket sizes"""res = '[ 'for b in bucks:if b != 0:res += str(b)res += ' 'res += ']'print(res)def buckets(text, sigma):"""Find the alphabet and the sizes of the bucket for each character in the text"""alpha = []bucket_sizes = array('L', [0] * sigma)for c in text:bucket_sizes[c] += 1for i in range(sigma):if bucket_sizes[i] != 0:alpha.append(i)# print_buckets(bucket_sizes)return alpha, bucket_sizesdef bucket_intervals(alpha, bucket_sizes, sigma):"""Computes the bucket intervals, i.e heads and tails"""heads = array('l', [0] * sigma)tails = array('l', [0] * sigma)j = 0for i in range(len(alpha)):heads[alpha[i]] = jj += bucket_sizes[alpha[i]]tails[alpha[i]] = j - 1# print_buckets(heads)# print_buckets(tails)return heads, tailsdef induced_sorting(lms, tails, heads, SA, type_suffix, text, n, m, alpha, bucket_sizes, sigma):"""Inductively creates the suffix array based on LMSArgs:lms: an array indicating the positions of LMS Blocks/Suffixes in texttails: an array indexed by the characters in T which tells the ends of the bucketsheads: an array indexed by the characters in T which tells the fronts of the buckets of those charactersSA: an empty array to be filled during the creation of the suffix arraytype_suffix: an array in which type_suffix[i] tells the type of text[i]text: the input whose suffix array is to be createdn: the length of the input 'text'alpha: an array of the alphabet of T in sorted orderbucket_sizes: an array containing the sizes of each bucket: Used in resetting heads, tails"""for i in range(m-1, -1, -1): # place LMS suffixes at the end of their bucketsnfs = tails[text[lms[i]]]SA[nfs] = lms[i]tails[text[lms[i]]] -= 1for i in range(n): # place the L-type suffixes at the fronts of their bucketsif SA[i] > 0 and type_suffix[SA[i] - 1] == L_TYPE:nfs = heads[text[SA[i] - 1]]SA[nfs] = SA[i] - 1heads[text[SA[i] - 1]] += 1# reset bucket countersheads, tails = bucket_intervals(alpha, bucket_sizes, sigma)for i in range(n-1, -1, -1): # place the S-type suffixes at the ends of their bucketsif SA[i] > 0 and type_suffix[SA[i] - 1] == S_TYPE:nfs = tails[text[SA[i] - 1]]SA[nfs] = SA[i] - 1tails[text[SA[i] - 1]] -= 1def blocks_are_equal(i, j, types, text, n):"""Testing for the equality of two blocks"""while i < n and j < n:if text[i] == text[j]:if is_lms(i, types) and is_lms(j, types):return Trueelse:i += 1j += 1else:return Falsereturn Falsedef get_reduced_substring(types, SA, lms, ordered_lms, text, n, m):"""Finds the reduced substring"""j = 0for i in range(n):if is_lms(SA[i], types):ordered_lms[j] = SA[i]j += 1# number the lms blocks and form the reduced substringpIS = array('l', [0] * m)k, i = 1, 1pIS[0] = 0for i in range(1, m):if text[ordered_lms[i]] == text[ordered_lms[i - 1]] and \blocks_are_equal(ordered_lms[i] + 1, ordered_lms[i - 1] + 1, types, text, n):pIS[i] = pIS[i - 1]else:pIS[i] = kk += 1# form the reduced substringinverse_lms = array('l', [0] * n)for i in range(m):inverse_lms[ordered_lms[i]] = pIS[i]for i in range(m):pIS[i] = inverse_lms[lms[i]]return pIS, k == m, k + 1def construct_suffix_array(T, SA, n, sigma):"""Constructs the suffix array of T and stores it in SAArgs:T: the text whose suffix array is to be builtSA: the array to be filledn: the length of T and SAsigma: the size of the alphabet of T, i.e the largest value in T"""if len(T) == 1: # special caseSA[0] = 0return SAt = classify(T, n) # step 1: classificationlms = find_lms_suffixes(t, n) # step 2: finding the indices of LMS suffixesm = len(lms)# print_types(t)alpha, sizes = buckets(T, sigma) # finding the bucket sizes and alphabet of Theads, tails = bucket_intervals(alpha, sizes, sigma)induced_sorting(lms, tails, heads, SA, t, T, n, m, alpha, sizes, sigma) # first induced sortordered_lms = array('L', [0] * len(lms))reduced_text, blocks_unique, sigma_reduced = get_reduced_substring(t, SA, lms, ordered_lms, T, n, m)reduced_SA = array('l', [-1] * m) # reduced SAif blocks_unique: # base case# compute suffix array manuallyfor i in range(m):reduced_SA[reduced_text[i]] = ielse:construct_suffix_array(reduced_text, reduced_SA, m, sigma_reduced)# use the suffix array to sort the LMS suffixesfor i in range(m):ordered_lms[i] = lms[reduced_SA[i]]heads, tails = bucket_intervals(alpha, sizes, sigma) # reset bucket tails and headsfor i in range(n): SA[i] = 0 # clear suffix arrayinduced_sorting(ordered_lms, tails, heads, SA, t, T, n, m, alpha, sizes, sigma)def bwt(T, SA: array, BWT: bytearray, n: int):"""If SA[i] = 0 then T[SA[i] - 1] = T[0 - 1] = T[-1] = '$"""for i in range(n):BWT[i] = T[SA[i] - 1]def isa(SA, ISA, n):"""Constructs an inverse suffix array"""for i in range(n):ISA[SA[i]] = idef fm_index(SA, ISA, LF, n):"""Constructs a last-to-first column mapping in linear time"""for i in range(n):if SA[i] == 0:LF[i] = 0else:LF[i] = ISA[SA[i] - 1]def naive_suffix_array(s, n):"""Naive suffix array implementation, just as a sanity check"""sa_tuple = sorted([(s[i:], i) for i in range(n)])return array('l', map(lambda x: x[1], sa_tuple))'''
text: str
return: sa
'''
def SAIS_sa(text):text += '$'text = [ord(c) for c in text]sigma = max(text) + 1n = len(text)SA = array('l', [-1] * n)construct_suffix_array(text, SA, n, sigma)bt = bytearray(n)bwt(text, SA, bt, n)return SA.tolist()[1:]'''
text: str
return: sa,rk,h
'''
def SAIS_sa_rk_h(text):sa = SAIS_sa(text)n,k = len(sa),0rk,h = [0]*n,[0]*nfor i,sa_i in enumerate(sa):rk[sa_i] = ifor i in range(n):if k>0: k-=1while i+k<n and sa[rk[i]-1]+k<n and text[i+k]==text[sa[rk[i]-1]+k]:k+=1h[rk[i]] = kreturn sa,rk,hclass Solution:def longestDupSubstring(self, T: str) -> str:sa,rk,h = SAIS_sa_rk_h(T)max_h = max(h)start_index = sa[h.index(max_h)]return T[start_index:start_index+max_h]ST表解法
模板
from typing import Callable, Generic, List, TypeVarE = TypeVar("E")class SlidingWindowAggregation(Generic[E]):"""SlidingWindowAggregationApi:1. append value to tail,O(1).2. pop value from head,O(1).3. query aggregated value in window,O(1)."""__slots__ = ["_stack0", "_stack1", "_stack2", "_stack3", "_e0", "_e1", "_size", "_op", "_e"]def __init__(self, e: Callable[[], E], op: Callable[[E, E], E]):"""Args:e: unit elementop: merge function"""self._stack0 = []self._stack1 = []self._stack2 = []self._stack3 = []self._e = eself._e0 = e()self._e1 = e()self._size = 0self._op = opdef append(self, value: E) -> None:if not self._stack0:self._push0(value)self._transfer()else:self._push1(value)self._size += 1def popleft(self) -> None:if not self._size:returnif not self._stack0:self._transfer()self._stack0.pop()self._stack2.pop()self._e0 = self._stack2[-1] if self._stack2 else self._e()self._size -= 1def query(self) -> E:return self._op(self._e0, self._e1)def _push0(self, value):self._stack0.append(value)self._e0 = self._op(value, self._e0)self._stack2.append(self._e0)def _push1(self, value):self._stack1.append(value)self._e1 = self._op(self._e1, value)self._stack3.append(self._e1)def _transfer(self):while self._stack1:self._push0(self._stack1.pop())while self._stack3:self._stack3.pop()self._e1 = self._e()def __len__(self):return self._size1、按位或最大的最小子数组长度
class Solution:def smallestSubarrays(self, nums: List[int]) -> List[int]:n = len(nums)Sm = SlidingWindowAggregation(lambda: 0, lambda a, b: a | b)for i in range(n):Sm.append(nums[i])res, j = [0] * n, 0S = SlidingWindowAggregation(lambda: 0, lambda a, b: a | b)for i in range(n):S.append(nums[i])while j <= i and S and S.query() == Sm.query():res[j] = i - j + 1S.popleft()Sm.popleft()j += 1return res2、使数组所有元素变成 1 的最少操作次数
class Solution:def minOperations(self, nums: List[int]) -> int:if gcd(*nums) != 1:return -1if 1 in nums:return len(nums) - nums.count(1)return minLen(nums) - 1 + len(nums) - 1def minLen(nums: List[int]) -> int:"""gcd为1的最短子数组.不存在返回INF."""n = len(nums)S = SlidingWindowAggregation(lambda: 0, gcd)res, n = inf, len(nums)for right in range(n):S.append(nums[right])while S and S.query() == 1:res = min(res, len(S))S.popleft()return res