基础算法：滑动窗口_python版本
能使用滑动窗口的题，基本都需要数字为正整数，这样才能保证滑入一个数字总和是增加的(单调性)
一、209. 长度最小的子数组
- 思路：
已每个位置为右端点，依次加大左端点，最短不满足 sum(num[left,right]) < target的。 - 代码：
class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: n = len(nums) ans = n + 1 # 也可以写 inf s = left = 0 for right, x in enumerate(nums): # 枚举子数组右端点 s += x while s >= target: # 满足要求 ans = min(ans, right - left + 1) s -= nums[left] left += 1 # 左端点右移 return ans if ans <= n else 0二、713. 乘积小于 K 的子数组
- 思路：
和上一题一样，站在每个右端点，去找符合要求的左端点。 - 代码：
class Solution: def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: if k <= 1: return 0 ans = left = 0 prod = 1 for right, x in enumerate(nums): prod *= x while prod >= k: # 不满足要求 prod //= nums[left] left += 1 ans += right - left + 1 return ans三、3. 无重复字符的最长子串
- 思路1：
还是一样，站在每个右端点，如果当前串内有重复的字符。依次移除左端点的 - 代码：
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: ans = left = 0 cnt = defaultdict(int) # 维护从下标 left 到下标 right 的字符及其出现次数 for right, c in enumerate(s): cnt[c] += 1 while cnt[c] > 1: # 窗口内有重复字母 cnt[s[left]] -= 1 # 移除窗口左端点字母 left += 1 # 缩小窗口 ans = max(ans, right - left + 1) # 更新窗口长度最大值 return ans- 思路2：
依次遍历s，不是重复字符直接加入并计算长度，遇到重复字符，那么当前字符要退出到上一个重复位置。列表可采用 list.index(i)，找到i字符在列表中的位置。 - 代码：
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: tmp_s = [] max_len = 0 for i in s: if i not in tmp_s: tmp_s.append(i) max_len = max(max_len, len(tmp_s)) else: index = tmp_s.index(i) tmp_s = tmp_s[index+1:] tmp_s.append(i) return max_len
