算法---滑动窗口

以下是对滑动窗口相关题目的总结：

3. 无重复字符的最长子串 - 力扣（LeetCode）

class Solution: def lengthOfLongestSubstring(self, s: str) -> int: char_set=set() max_len=0 left=0 for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left+=1 char_set.add(s[right]) max_len=max(max_len,right-left+1) return max_len

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: res=[] len_s,len_p=len(s),len(p) if len_s<len_p: return res count_s=[0]*26 count_p=[0]*26 for ch in p: count_p[ord(ch)-ord('a')]+=1 for i in range(len_s): count_s[ord(s[i])-ord('a')]+=1 #保证窗口大小为len(p) if i>=len_p: count_s[ord(s[i-len_p])-ord('a')]-=1 if count_p==count_s: res.append(i-len_p+1) return res

560. 和为 K 的子数组 - 力扣（LeetCode）

针对这一题，如果数组都是非负整数，那么可以用滑动窗口：

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: left=0 num=0 sums=0 for right in range(len(nums)): sums+=nums[right] while sums>k and left<=right: sums-=nums[left] left+=1 if sums==k and left<=right: #这里left<=right不能漏写，否则k=0时，sums=k=0,num=1 num+=1 return num

但如果数组中存在负整数，那么就不能用滑动窗口了，而是要用前缀和。不明白思路可以看看这个视频：

算法面试实录-和为 k 的子数组_哔哩哔哩_bilibili

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: # 哈希表：键为前缀和，值为该前缀和出现的次数 prefix_count = {0: 1} # 初始化：前缀和为0出现1次 prefix_sum = 0 count = 0 for num in nums: # 计算当前前缀和 prefix_sum += num # 查找是否存在前缀和为 prefix_sum - k # 如果存在，说明从这些前缀和的下一个位置到当前位置的子数组和为k if prefix_sum - k in prefix_count: count += prefix_count[prefix_sum - k] # 更新当前前缀和的计数 prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1 return count