Leetcode（滑动窗口习题思路总结，持续更新。。。）
讲解题目：长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target ，找出该数组中满足其和 ≥ target 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: target = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
这类型题类似于规划问题，有约束（和 >= targrt），有目标函数（长度最小）
暴力解题思路
就是首先遍历窗口从1到len(nums)，然后再遍历该窗口长度下的所有数组，计算和，因为窗口长度从小遍历，所以只要出现和 >= target 就结束计算，时间复杂度是N2
def minSubArrayLen(target, nums):
for win in range(1, len(nums) + 1):
# print(f'win:{win}')
for left in range(len(nums) - win + 1):
left = max(0, left)
right = min(left + win, len(nums))
val = nums[left:right]
if sum(val) >= target:
return win
else:
pass
return 0改进解题思路
- 初始化 left = right = 0，把区间 [left, right] 称为一个「窗口」。
- 不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求。
- 停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求。
- 重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
def minSubArrayLen(s, nums):
start = 0
end = 0
min_length = len(nums) + 1
sum_nums = 0
while end < len(nums):
sum_nums += nums[end]
while sum_nums >= s:
min_length = min(min_length, end - start + 1)
sum_nums -= nums[start]
start += 1
end += 1
return 0 if min_length == len(nums) + 1 else min_length习题1
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串
示例
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
思路：
-
滑动窗口：我们维护一个可变的窗口，这个窗口的左右边界分别用指针 start 和 end 表示。我们通过移动 end 指针来扩大窗口，直到窗口包含 T 中所有的字母。然后，我们尝试通过移动 start 指针来缩小窗口，以得到最小的满足条件的子串。
-
字符频率：我们需要记录 T 中字符的频率，并在窗口中保持一个字典来统计窗口内的字符频率。每当窗口内的字符完全满足 T 中所有字符时，我们就更新最小子串的长度。
def minSubArrayLen(S, T):
if not S or not T:
return ''
t_dic = Counter(T)
start = 0
flag = 0
min_len = float('inf')
min_substr = ''
s_dic = Counter()
for end in range(len(S)):
char = S[end]
s_dic[char] += 1
# print(f'sub_str:{sub_str}')
# print(f's_dic:{s_dic}')
if char in t_dic.keys() and t_dic[char] == s_dic[char]:
flag += 1
# print(f'flag:{flag}')
while flag == len(t_dic) and start <= end:
if end - start + 1 <= min_len:
min_len = end - start + 1
min_substr = S[start:end + 1]
else:
pass
# print(f'min_substr:{min_substr}')
s_dic[S[start]] -= 1
if S[start] in t_dic.keys() and t_dic[S[start]] > s_dic[S[start]]:
flag -= 1
start += 1
# print(f's_dic:{s_dic}')
# print(f'flag:{flag}')
# print(f'res_final:{res_final}')
return min_substr习题2
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
子数组的长度是 k，且
子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
子数组 是数组中一段连续非空的元素序列。
示例
输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：nums 中长度为 3 的子数组是：
- [1,5,4] 满足全部条件，和为 10 。
- [5,4,2] 满足全部条件，和为 11 。
- [4,2,9] 满足全部条件，和为 15 。
- [2,9,9] 不满足全部条件，因为元素 9 出现重复。
- [9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。思路：
- 用字典 nums_dic 维护窗口内元素的个数，用 max_sum 维护窗口内的数之和
- 遍历数组，窗口进入进出一个元素（需要维护 nums_dic 和 max_sum），若满足条件（len（nums_dic）== k）则更新 max_val
def maximumSubarraySum(nums, k):
if len(nums) == 0 or k == 0:
return 0
if k == 1:
return max(nums)
max_val = float('-inf')
nums_dic = Counter(nums[:k-1])
max_sum = sum(nums[:k-1])
for i in range(k - 1, len(nums)):
nums_dic[nums[i]] += 1
max_sum = max_sum + nums[i]
# print(f'nums_dic:{nums_dic}')
# print(f'max_sum:{max_sum}')
if len(nums_dic) == k:
max_val = max(max_sum, max_val)
nums_dic[nums[i - k + 1]] -= 1
if nums_dic[nums[i - k + 1]] == 0:
del nums_dic[nums[i - k + 1]]
max_sum -= nums[i - k + 1]
return 0 if max_val == float('-inf') else max_val