滑动窗口
About 4 min
209. 长度最小的子数组 - 力扣（LeetCode）
题目描述：有 n 个正整数数组和一个正整数 target， 找出数组中满足其总和大于等于 target 的最小的 子数组（子数组：连续的数组）
- 方法一：双指针，从右开始滑动， 如果现有的和大于了
target就将左指针向右滑动。时间复杂度O(n),左和右最多移动 n 次， 空间复杂度O(1) - 方法二：暴力法，每个下标开始依次求和，大于等于
target后就更新最小长度。 - 方法三： 前缀和 + 二分 这里其实就是暴力法的改良，对于求和操作进行改良，因为题目条件说过所有的数都是正整数，所以可以维护一个前缀和数组，在前缀和数组上二分。
注意：
这里简单用滑动窗口, 这个窗口是右 for 左 while的.
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_length = 10**6
sum = 0
left = 0
for right in range(len(nums)):
sum += nums[right]
while sum >= target:
min_length = (
(right - left + 1)
if (right - left + 1) < min_length
else min_length
)
sum -= nums[left]
left += 1
min_length = min_length if min_length != 10**6 else 0
return min_length
76. 最小覆盖子串 - 力扣（LeetCode）
题目描述：给你两个字符串 S 和 T， 返回 S 中涵盖 T 中所有字符的最小子串。
- 方法一：滑动窗口，右
for满足需求后就开始左while来更新。满足需求函数写个字典来记录。 - 方法二：
- 方法三：
注意：
这题主要需要考虑的是t中出现重复字符的问题, 我的解决方法是做个字典, 来供删除,
实际做起来还是比较清晰的, 就是窗口移动时的逻辑需要判断, 个人感觉可以一边写一边 print 不断调试
class Solution:
def minWindow(self, s: str, t: str) -> str:
curr = self.constrcut_t(t)
right = 0
return_str = ""
min_length = 10**5
for i in range(len(s)):
while not self.is_satisfied(curr) and right < len(s):
if s[right] in curr:
curr[s[right]] -= 1
right += 1
if right - i < min_length and self.is_satisfied(curr):
return_str = s[i:right]
min_length = right - i
if s[i] in curr:
curr[s[i]] += 1
return return_str
def is_satisfied(self, curr: dict):
for key, value in curr.items():
if value >= 1:
return False
return True
def constrcut_t(self, t):
cur = {}
for i in range(len(t)):
if t[i] in cur:
cur[t[i]] += 1
else:
cur[t[i]] = 1
return cur
ts 实现,发现 ts 再做的时候比第一遍好看多了
function minWindow(s: string, t: string): string {
let dir: { [key: string]: number } = {};
for (let i = 0; i < t.length; i++) {
if (t[i] in dir) {
dir[t[i]] += 1;
} else {
dir[t[i]] = 1;
}
}
let l = 0;
let r = 0;
let min = 10 ** 5;
let returnString = "";
for (let r = 0; r < s.length; r++) {
if (s[r] in dir) {
dir[s[r]] -= 1;
}
while (isSatisfied(dir) && l <= r) {
if (r - l < min) {
min = r - l;
returnString = s.slice(l, r + 1);
}
if (s[l] in dir) {
dir[s[l]] += 1;
}
l += 1;
}
}
return returnString;
}
function isSatisfied(dir: { [key: string]: number }): boolean {
for (let item of Object.values(dir)) {
if (item > 0) {
return false;
}
}
return true;
}
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
题目描述：给定两个字符串 s 和 p，找出 s 中所有 p 的异位词的子串，返回子串的索引。
- 方法一： 定长滑动窗口。
- 方法二：
- 方法三：
注意：
这种题目还是要注意构造一个 dist 来记录存在过的字符, 只要考虑到滑动窗口就行了, 不要给自己上难度.
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
right = 0
curr = self.construct(p)
return_list = []
for left in range(len(s) - len(p) + 1):
while right - left < len(p):
if s[right] in curr:
curr[s[right]] -= 1
if self.is_satisfied(curr):
return_list.append(left)
right += 1
if s[left] in curr:
curr[s[left]] += 1
return return_list
def is_satisfied(self, curr):
for key, value in curr.items():
if value != 0:
return False
return True
def construct(self, p):
dir = {}
for i in range(len(p)):
if p[i] in dir:
dir[p[i]] += 1
else:
dir[p[i]] = 1
return dir
930. 和相同的二元子数组 - 力扣（LeetCode）
题目描述 ： 一个数组全部是由 0 和 1 组成的， 求所有和等于 target 的子数组。
- 方法一：前缀和 + 哈希表， 做个前缀和的数组，遍历该数组，更新哈希表， 如果数组里有
preSum-goal，就更新count。 - 方法二：使用滑动窗口，
恰有x个元素的窗口=最多含x个元素的窗口-最多含x-1个元素的窗口 - 方法三：
注意：
拼尽全力也无法战胜, 我真的哭死
class Solution:
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
sum = 0
left = 0
count = 0
for r in range(len(nums)):
sum += nums[r]
while sum > goal and left < r:
sum -= nums[left]
left += 1
temp = left
if sum == goal:
temp = left
while temp <= r:
if nums[temp] == 0:
count += 1
elif nums[temp] == 1:
count += 1
break
temp += 1
return count
之所以做不出来是因为 temp=left 这里回头了
全新方法:
这个窗口为什么不行, 因为你在强行构造 恰有x个元素的窗口, 实际上恰有x个元素的窗口 = 最多含x个元素的窗口- 最多含x-1个元素的窗口
而这个 最多元素 的窗口可以不用回头的窗口构建!!!, 这个思维转变非常关键
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
def at_most(nums, goal):
if goal < 0:
return 0
res = 0
count = 0
left = 0
for right in range(len(nums)):
count += nums[right]
while count > goal:
count -= nums[left]
left += 1
res += right - left + 1
return res
return at_most(nums, goal) - at_most(nums, goal - 1)