代码随想录数组二刷:长度最小的子数组(滑动窗口)
leetcode209
这道题采用滑动窗口的思想去做。
实现滑动窗口,主要确定如下三点:
- 窗口内是什么?
- 如何移动窗口的起始位置?
- 如何移动窗口的结束位置?
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。窗口的起始位置如何移动:如果当前窗口的值大于等于s了,窗口就要向前移动了(也就是该缩小了)。窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。
具体代码如下:
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
l = len(nums)
left,right = 0,0
min_len = float('inf')
cur_sum = 0
while right < l:
cur_sum += nums[right]
while cur_sum >= target:
min_len = min(min_len, right - left + 1)
cur_sum -= nums[left]
left += 1
right += 1
return min_len if min_len!=float('inf') else 0
接下来来具体分析这个代码,因为是滑动窗口,那么这个窗口是怎么构成的呢,是不是就是left和right组成的区间长度,那么何时去计算这个长度,是不是区间里面的和大于等于target时候开始去计算长度。也就是:while cur_sum >= target
,然后左边开始移动,移动的原因是因为这个和可能远超你要求的target,所以可以移动左边来缩小窗口。由于你左边移动了,就要把个值从总体的和剔除掉。那么啥时候退出这个内部循环呢。也就是求出的和小于target时候,就去移动右边界。
下面来看水果成篮这道题:
leetcode904
这道题也是采用滑动窗口去解决问题。在做这道题时候,要明白几个问题才能去做好这道题
- 窗口内是什么?
- 如何移动窗口的起始位置?
- 如何移动窗口的结束位置?
这道题窗口内就是能摘的树的数量。但是数组里面的数字相当于是标记一样,这里要用到哈希表去记录一下。因为最多两个篮子,所以种类最多是两种。当超过两个篮子时候,左边窗口开始移动,同时哈希表关于该项的值要减去1,如果该项的值为0,则删除这一项。
具体代码如下:
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
count = collections.defaultdict(int)
left,max_len,right = 0,0,0
while right < len(fruits):
count[fruits[right]] += 1
while len(count) > 2:
count[fruits[left]] -= 1
if count[fruits[left]] == 0:
del count[fruits[left]]
left += 1
max_len = max(max_len, right - left + 1)
right += 1
return max_len
代码步骤解析
初始化变量:
count
:defaultdict(int)
,用于记录窗口内每种水果的数量。left
和right
:窗口的左右边界。max_len
:记录遇到的最大窗口长度。
扩展窗口:
- 使用
right
指针遍历fruits
数组,每次循环中将fruits[right]
加入到窗口(即哈希表count
中增加对应水果的计数)。
- 使用
调整窗口大小:
- 当哈希表中的键(即水果类型)数量超过 2 时,开始移动
left
指针缩小窗口,直到窗口内的水果类型数不超过两种。 - 如果某种水果的数量减到 0,则从哈希表中删除该水果。
- 当哈希表中的键(即水果类型)数量超过 2 时,开始移动
更新最大长度:
- 在每次循环的末尾,更新
max_len
为当前窗口的长度(right - left + 1
)和已记录的max_len
中的较大值。
- 在每次循环的末尾,更新
返回结果:
- 循环结束后,返回
max_len
作为最大可以摘的水果数量。
- 循环结束后,返回
性能分析
- 时间复杂度:O(N),其中 N 是
fruits
数组的长度。尽管内部有一个 while 循环来调整窗口大小,但每个元素最多被加入和删除一次。 - 空间复杂度:O(1),虽然使用了哈希表,但由于最多只存储两种水果的计数,所以空间复杂度为常数。
下面继续来看一道题;
leetcode76
这道题也是用滑动窗口+哈希表去做。首先s的长度小于t的长度是一定不满足的,直接返回空字符串即可。
外层while循环依旧控制窗口右边界,内层循环控制左边界。只不过这道题需要用到哈希表记录t对应字符个数。具体代码如下:
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(s) < len(t):
return ""
hash_t = collections.defaultdict(int)
hash_s = collections.defaultdict(int)
min_len = float('inf')
min_window = ""
left,right,formed= 0,0,0
for i in range(len(t)):
hash_t[t[i]] += 1
hash_t_lenth = len(hash_t)
while right < len(s):
hash_s[s[right]] += 1
if s[right] in hash_t and hash_s[s[right]] == hash_t[s[right]]:
formed += 1
while formed == hash_t_lenth:
if right - left + 1 < min_len:
min_len = right - left + 1
min_window = s[left:right+1]
hash_s[s[left]] -= 1
if hash_s[s[left]] < hash_t[s[left]]:
formed -= 1
left += 1
right += 1
return min_window
下面继续看几道滑动窗口相关的题目:
leetcode3
具体代码如下:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left,right = 0,0
maxlen = 0
hashmap = collections.defaultdict(int)
while right < len(s):
hashmap[s[right]] += 1
while hashmap[s[right]] > 1:
hashmap[s[left]] -= 1
if hashmap[s[left]] == 0:
del hashmap[s[left]]
left += 1
maxlen = max(maxlen, right - left + 1)
right += 1
return maxlen