基础算法：滑动窗口_python版本

能使用滑动窗口的题，基本都需要数字为正整数，这样才能保证滑入一个数字总和是增加的(单调性)

一、209. 长度最小的子数组

• 思路：
  已每个位置为右端点，依次加大左端点，最短不满足 sum(num[left,right]) < target的。
• 代码：

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:n = len(nums)ans = n + 1  # 也可以写 infs = left = 0for right, x in enumerate(nums):  # 枚举子数组右端点s += xwhile 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 0ans = left = 0prod = 1for right, x in enumerate(nums):prod *= xwhile prod >= k:  # 不满足要求prod //= nums[left]left += 1ans += right - left + 1return ans

三、3. 无重复字符的最长子串

• 思路1：
  还是一样，站在每个右端点，如果当前串内有重复的字符。依次移除左端点的
• 代码：

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:ans = left = 0cnt = defaultdict(int)  # 维护从下标 left 到下标 right 的字符及其出现次数for right, c in enumerate(s):cnt[c] += 1while 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 = 0for 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