算法

• 滑动窗口
• • 1.利用滑动窗口解题
  • 2.两种解法
  • • 第一种 — 暴力
    • 第二种 — 滑动窗口
  • 3.总结
  • • python
    • 算法
  • 4.相关题目推荐

leetcode题目链接

所谓滑动窗口，就是不断地调节子序列的起始位置和终止位置，从而得出我们想要的结果，虽然都是使用双指针，但与上一个移除元素的双指针不同的是，这个更关注使得[slowindex,fastindex]之间的数值有效

时间复杂度：O(n^2)
空间复杂度：O(1)

思路：开两层for循环，从头到尾分别遍历slowindex和fastindex使得所有可行解都被找到，比较长度即可

时间复杂度：O(n)
空间复杂度：O(1)

思路：如下图

代码如下：

def minSubArrayLen(nums,target):
	slowindex = 0 # 慢指针
    sum = 0 # 记录窗口内数的和
    length = float("inf") # 距离初始化为一个很大的数

    for fastindex in range(len(nums)):
        sum += nums[fastindex] # 每次遍历都加上当前数
        while(sum>=target):# 如果和大于等于了target，就要将slowindex向前滑动，直到sum=target的情况就返回length，否则就返回0

1. list和str和互相转换

   list -> string ：

    str = "".join(lst)
   

   string -> list

    lst = list(str)
   

2. python3中字典是带顺序的

   小技巧：有时候用list中元组的方式可能比用dist更方便，因为可以使用索引来操作

   即用 [(a,b),(c,d),…] 代替 {a:b,c:d,…}

实现滑动窗口需要确定的：

1. 窗口内是什么？ 本题中：满足其和 ≥ s 的长度最小的 连续 子数组。
2. 如何移动窗口的起始位置？ 本题中：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
3. 如何移动窗口的结束位置？本题中：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。

904.水果成篮
76.最小覆盖子串