滑动窗口模板
class Solution:
def slidingWindow(self, nums: List[int]) -> int:
"""
step1:根据题意维护变量
1.和 Sum
2.最大长度 max_len，最小长度 min_len
3.不重复 hashmap = {}
step2: 窗口的开始位置start和结束位置end
step3: 根据条件写判断语句，维护step1中的变量
step4: 根据题目要求，从中选择一种方法套用
选择一：窗口长度固定
if 窗口长度达到限定的长度：
1.更新step1中的相关变量
2.窗口左边位置start向前移动 1，保证end向右移动时窗口长度保持不变
选择二：窗口长度不固定
while 窗口条件不符合：
1.更新step1中的相关变量
2.不断移动start，直到窗口条件符合
step5:
返回答案
"""
- 分析：遍历数组，不能对每次求平均值比较，会超时，需要先计算求和，且求和比较每次加上新加入的那个数并减去窗口第一个数，最后再将最大和求平均
- 题解
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
cur_sum = sum(nums[:k])
max_sum = cur_sum
for i in range(k, len(nums)):
cur_sum = cur_sum + nums[i] - nums[i - k]
max_sum = max(cur_sum, max_sum)
max_avr = max_sum / k
return max_avr
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
stack = []
ans = 0
l = len(s)
for i in range(l):
if s[i] in stack:
while stack[0] != s[i]:
stack.pop(0)
stack.pop(0)
stack.append(s[i])
ans = max(ans, len(stack))
return ans
- 分析：定义一个存储最小长度的变量，求和变量，子数组开始位置，然后for循环遍历结尾位置。每次遍历对加入的索引数组求和，如果大于等于目标后，就返回最小长度为当前长度与最小长度的较小的，然后循环判断sum是否大于target，满足的话依次去除第一个元素。
- 本质：对于求子串长度最大最小的问题其实可以通过栈或队列的方式来解决
- 题解：
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_len = float("inf")
sum = 0
start = 0
for end in range(len(nums)):
sum += nums[end]
if sum >= target:
min_len = min(min_len, end - start + 1)
while sum >= target:
min_len = min(min_len, end - start + 1)
sum -= nums[start]
start += 1
if min_len == float("inf"):
return 0
return min_len
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
#step1:
ans = []
hashmap = {}
start = 0
#step2:
hashmap_p = {}
for item in p:
hashmap_p[item] = hashmap_p.get(item,0) + 1
for end in range(len(s)):
#step3:
hashmap[s[end]] = hashmap.get(s[end],0) + 1
if hashmap == hashmap_p:
ans.append(start)
#step4:长度固定
if end + 1 >= len(p):
head = s[start]
hashmap[head] -=1
if hashmap[head] == 0:
del hashmap[head]
start +=1
return ans
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
m, n, ans = len(s), len(p), list()
if m < n: return ans
book_s, book_p = [0] * 26, [0] * 26
for i in range(n):
book_s[ord(s[i])-ord('a')] += 1
book_p[ord(p[i])-ord('a')] += 1
for i in range(n, m):
if book_s == book_p: ans.append(i-n)
book_s[ord(s[i-n])-ord('a')] -= 1
book_s[ord(s[i])-ord('a')] += 1
if book_s == book_p: ans.append(m-n)
return ans
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
hashmap = {}
hashmap_s1 = {}
start = 0
for i in range(len(s1)):
hashmap_s1[s1[i]] = hashmap_s1.get(s1[i], 0) + 1
for end in range(len(s2)):
hashmap[s2[end]] = hashmap.get(s2[end], 0) + 1
if hashmap == hashmap_s1:
return True
if end + 1 >= len(s1):
hashmap[s2[start]] -= 1
if hashmap[s2[start]] == 0:
del hashmap[s2[start]]
start += 1
return False
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
#step1：定义变量
Sum = 0
max_score = float("-inf")
hashmap = {}
#step2: 定义起始位置start和结束位置end
start = 0
for end in range(len(nums)):
Sum +=nums[end]
hashmap[nums[end]] = hashmap.get(nums[end],0) + 1
#step3:
if len(hashmap) == end - start + 1:
max_score = max(max_score,Sum)
#step4：长度不固定
while end - start + 1 > len(hashmap):
head = nums[start]
hashmap[head] -=1
if hashmap[head] == 0:
del hashmap[head]
Sum -= nums[start]
start +=1
return max_score
