滑动窗口算法_滑动窗口算法
形如 LeetCode第209题：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。 示例:输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。或者是形如 LeetCode第3题 无重复字符的最长子串：给定一个字..
·
形如 LeetCode第209题：
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
或者是形如 LeetCode第3题 无重复字符的最长子串：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
这两道题目都是给出一个数组，要求找到数组中连续的一段满足相应条件的子数组中长度最大值或者最小值。
这一类型的题目都可以用滑动窗口算法来进行解决。首先判断条件
- 我们定义
是向上包含的，如果
那么
；
- 我们定义
是向下包含的，如果
那么
。
我们不妨假设对于向上包含的问题，
通过这个定义我们知道，209题是向上包含的，3题（无重复字符的最长子串）是向下包含的。
向上包含的问题解决方法是：
# i: left pointer, j: right pointer, arr: array, n: length of arr
i, j = 0, 0
min_len = n + 1
for j in [0, 1, ..., n-1]:
while f(arr[i, i+1, ..., j]]) == 1:
min_len = min(min_len, j - i + 1)
i += 1
if min_len == n+1:
# Not Found
return -1
else:
return min_len可以通过数学归纳法证明，在每
我们定义当
关于
向下包含的问题解决方法是：
# i: left pointer, j: right pointer, arr: array, n: length of arr
i, j = 0, 0
max_len = 0
for j in [0, 1, ..., n-1]:
while f(arr[i, i+1, ..., j]) == 0:
i += 1
max_len = max(max_len, j - i + 1)
return max_len比如对于对于LeetCode第904题：
这是一个向下包含问题，因此可以用滑动窗口法解决：
def totalFruit(self, tree: List[int]) -> int:
i, j = 0, 0
max_len = 0
n = len(tree)
fruit_number = [0] * n
K = 0
for j in range(n):
if fruit_number[tree[j]] == 0:
K += 1
fruit_number[tree[j]] = fruit_number[tree[j]] + 1
if not K <= 2:
if fruit_number[tree[i]] == 1:
K -= 1
fruit_number[tree[i]] = fruit_number[tree[i]] - 1
i += 1
max_len = max(max_len, j - i + 1)
return max_len
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献8条内容
所有评论(0)