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

作者：Y1nhl

物联沃分享整理
物联沃-IOTWORD物联网 » Python实现滑动窗口算法详解