算法---滑动窗口

以下是对滑动窗口相关题目的总结3. 无重复字符的最长子串 - 力扣LeetCodeclass Solution: def lengthOfLongestSubstring(self, s: str) - int: char_setset() max_len0 left0 for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left1 char_set.add(s[right]) max_lenmax(max_len,right-left1) return max_len438. 找到字符串中所有字母异位词 - 力扣LeetCodeclass Solution: def findAnagrams(self, s: str, p: str) - List[int]: res[] len_s,len_plen(s),len(p) if len_slen_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 ilen_p: count_s[ord(s[i-len_p])-ord(a)]-1 if count_pcount_s: res.append(i-len_p1) return res560. 和为 K 的子数组 - 力扣LeetCode针对这一题如果数组都是非负整数那么可以用滑动窗口class Solution: def subarraySum(self, nums: List[int], k: int) - int: left0 num0 sums0 for right in range(len(nums)): sumsnums[right] while sumsk and leftright: sums-nums[left] left1 if sumsk and leftright: #这里leftright不能漏写否则k0时sumsk0,num1 num1 return num但如果数组中存在负整数那么就不能用滑动窗口了而是要用前缀和。不明白思路可以看看这个视频算法面试实录-和为 k 的子数组_哔哩哔哩_bilibiliclass 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