前言
滑动窗口
什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
相关题目如下表所示
| 题目 | |
|---|---|
| 53.最大子序和 | 简单 |
| 3.无重复字符的最长子串 | 中等 |
| 209.度最小的子数组 | 中等 |
| 219存在重复元素 | 中等 |
| 239/剑指 Offer 59 - I 滑动窗口最大值 | 困难 |
| 567. 字符串的排列 | 中等 |
| 718. 最长重复子数组 | 中等 |
| 402.替换后的最长重复字符 | |
| 30.串联所有单词的子串 | 困难 |
| 76. 最小覆盖子串 | 困难 |
1 leetcode53. 最大子序和
题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
解题思路：
动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
时间复杂度：O(n)
代码
class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num: nums) {
if(sum > 0) {
sum += num;
} else {
sum = num;
}
ans = Math.max(ans, sum);
}
return ans;
}
}复杂度分析
- 时间复杂度：O(n)，进行了一次遍历。
- 空间复杂度：O(1)。
2 leetcode3. 无重复字符的最长子串
题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。示例 4:
输入: s = ""
输出: 0解题思路
本题使用滑动窗口的思路。
步骤：
（1）start不动，end向后移动
（2）当end遇到重复字符，start应该放在位置=MAX（上一个重复字符的位置的后一位 map.get(nums[i]) + 1 ，原有位置start)的最大值，同时记录最长的长度ans。
这里解释下为啥子start需要取最大值：以 deedf 为例， 在经过第一轮判断e重复之后，start和end同时指向第二个e，end继续向后移，此时遇到了重复的d字符，但此时map中所包含的d的kv值仍是第一个d的为0，而此时start的位置为3。此时为了避免start指针回到了第一个位置，所以需要判断最大值使得指针不会回到最开始的d的位置,所以start=max(0+1,3)=3。 简单来说，一旦start的位置变更之后，对于start之前的元素仍是在map集合中的，如果没有经过比较，一旦end遇到了重复元素的情况会优先从map中存储的前面的字符查找，这并不是期望的结果
（3）怎样判断是否遇到重复字符，且怎么知道上一个重复字符的位置？–用哈希字典的key来判断是否重复，用value来记录该字符的最新位置。
代码
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
hashIndex={}#字典
start,ans=0,0
for end,v in enumerate(s):#end位置，v表示value
if v in hashIndex.keys():#重复
start=max(hashIndex.get(v)+1,start)
hashIndex[v]=end
ans=max(end-start+1,ans)
return ans复杂度分析
- 时间复杂度：O(n)，进行了一次遍历。
- 空间复杂度：O(n)，借助hash存储过程。
3 leetcode 219. 存在重复元素 II
题目描述
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]**，并且 i 和 j 的差的 **绝对值 至多为 k。
维护一个哈希表record，即滑动窗口，里面始终最多包含 k 个元素，当出现重复值时则说明在 k 距离内存在重复元素。每次遍历一个元素则将其加入哈希表中，如果哈希表的大小大于 k，则移除最前面的数字
示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:
输入: nums = [99,99], k = 2
输出: false
代码
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
record={}
start=0
for i,v in enumerate(nums):
if v in record.keys():#存在重复值则说明在 k 距离内存在重复元素
return True
#不在 就加进字典中
record[v]=i
if len(record)>k:#如果哈希表的大小大于 k，则移除最前面的数字
record.pop(nums[i-k])
return False复杂度分析
- 时间复杂度：O(n)，进行了一次遍历。
- 空间复杂度：O(k)，借助hash存储过程。
参考：
4 leetcode209长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
解法1 ：滑动窗口解法
解题思路
定义两个指针 start和 end分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum存储子数组中的元素和（即从 nums[start]到 nums[end] 的元素和）。
初始状态下，start和 end都指向下标 0，sum的值为 0。
每一轮迭代，将 nums[end] 加到 sum，如果sum≥target，则更新子数组的最小长度（此时子数组的长度是end−start+1），然后将 nums[start] 从 sum 中减去并将start 右移，直到sum<s，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将end 右移。
代码
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
n=len(nums)
start,end=0,0
sum=0
ans=n+1
while end<n:
sum=sum+nums[end]
while(sum>=target):# 大于target 去除滑动窗口前面的 直到之和小于target
ans = min(end - start + 1, ans)
sum=sum-nums[start]
start = start + 1
end=end+1
return 0 if ans==n+1 else ans复杂度分析
时间复杂度：O(n)，其中 n是数组的长度。指针start 和 end最多各移动n 次。
两个while的循环为什么是O(n)?
因为： 两个指针都是单调的向右移动，所以至多2n
内循环有触发条件，也就是说在遍历外循环的过程中，不是每次遍历都会触发内循环执行。也就是说内循环触发的次数是一个常量，随着n的规模变大，触发次数并不一定变大。也就是说，在内循环触发时，最坏情况下复杂度为n，但受到触发次数限制。 假设触发次数为常量A，按照上面最坏情况计算，总的执行次数可表示为N+AN=(A+1)N，(A+1)为常量，因此时间复杂度是O(n)
空间复杂度：O(1)。
解法2 ：前缀和+二分查找
解题思路
前缀和：为了使用二分查找，需要额外创建一个数组 sums 用于存储数组 nums 的前缀和，其中sums[i] 表示从nums[0] 到 nums[i] 的元素和。
例如nums = [2,3,1,2,4,3]中对应的sums=[0, 2, 5, 6, 8, 12]。
sums[0] = 0 意味着前 0 个元素的前缀和为 0
sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
得到前缀和之后，对于每个开始下标 i，可通过二分查找得到大于或等于i的最小下标mid，使得sums[bound]−sums[i]≥s，并更新子数组的最小长度:此时子数组的长度是bound−i。
代码
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
n=len(nums)
ans=n+1
sums = [0] * (n+1)
#得到前缀和
for i in range(1,n+1):
sums[i]=sums[i-1]+nums[i-1]
print(sums)
#在sums数组中使用二分查找 固定i 查找sums[bound]-sums[i]>=target，则子数组的长度是bound−i
#sums=[0, 2, 5, 6, 8, 12,15]
for i in range(n):
left = i
right =n
while(left<=right):
mid=left+(right-left)//2
if((sums[mid]-sums[i])==target):
ans=min(mid-i,ans)
break
elif((sums[mid]-sums[i])>target):#往左移动
ans=min(mid-i,ans)
right=mid-1
else:
left=mid+1
return 0 if ans==n+1 else ans复杂度分析
时间复杂度：O(nlogn)。
空间复杂度：O(1）
5 leetcode718. 最长重复子数组
给两个整数数组 A 和 B ，返回两个数组中 公共的、长度最长的子数组的长度。
示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
6 leetcode239. 滑动窗口最大值
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7