LeetCode算法—滑动窗口

一：滑动窗口

1、窗口：滑动窗口的核心就是一个窗口；通常使用两个指针表示（一个指向左边界；一个指向右边界）；窗口中的元素就是当前字串

2、滑动：窗口从数组或字符串的起始位置开始，逐步向右滑动。当窗口无法满足条件时，调整左边界以缩小窗口；当窗口满足条件时，尝试记录当前窗口的结果，并继续调整以找到可能更优的结果。

二：LeetCode

209 长度最小的数组

（1）题目：求连续最小的字串和大于目标值的最小长度

（2）思路：定义两个指针；left和right；定义sum表示窗口中的元素的和；min_length表示窗口中满足条件的字串的长度；然后遍历数组；填充窗口中的元素；当窗口中的元素大于目标值的时候；说明需要调整窗口；于是记录当前窗口的长度；然后将窗口左边第一个元素的值删除掉；left指针向前移动一位；继续判断；直至小于目标值的时候说明当前的长度就是满足条件的最小长度；返回mix_length的值；如果不存在直接返回0

def func(nums,target):
    left=0
    sum=0
    min_length=float('inf')
    for right in range(len(nums)):
        sum+=nums[right]#填充窗口
        while sum>=target:#滑动的条件
            min_length=min(min_length,right-left+1)
            sum-=nums[left]#弹出左端第一个元素
            left+=1
    return min_length if min_length!=float('inf') else 0

1456 定长字符串中元音的做大数目

（1）题目：请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数

（2）思路：首先记录前k的字符中元音字符的数量；然后利用滑动窗口；如果当前的窗口左端的元素为元音字母；那么count-1；入宫窗口的右端的元素为元音字母，count+1；然后取最大的值返回即可

def func(s,k):
    count=0
    vowels=('aeiou')
    for i in range(k):
        if i in vowels:
            count+=1
    max_count=count
    for i in range(k,len(s)):
        if s[i-k] in vowels:
            count-=1
        if s[i] in vowels:
            count+=1
        max_count=max(max_count,count)
    return max_count