总的来说,滑动窗口作为一种强大的数据处理技术,不仅在算法竞赛和数据科学领域中有着广泛的应用,在网络通信领域也扮演着重要的角色。通过有效的窗口管理和数据控制,可以显著提高数据处理效率和网络传输的稳定性。
滑动窗口,简而言之,是一个能够移动的容器,旨在通过遍历所有可能的情况来找出最优解。在这个过程中,关键是要及时排除那些非最优解的情况。以前面的例子为例,即使你已经满足了大佬对苹果数量的要求,你也需要及时地将多余的人从窗口中移除,这样才能够确保窗口中所呈现的始终是最优解。
给定一个含有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示例3:
输入:target=11,nums=[1,1,1,1,1,1,1,1]输出:0提示:
实现代码如下(看不懂可以回去看看漫画)
输入:nums=[10,5,2,6],k=100输出:8解释:8个乘积小于100的子数组分别为:[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。需要注意的是[10,5,2]并不是乘积小于100的子数组。示例2:
输入:nums=[1,2,3],k=0输出:0提示:
解题思路
此题与题目一类似,但需注意题目要求是严格小于k的连续子数组,且nums中的元素大于1。因此,当k小于等于1时,无法满足要求。当窗口元素为[n:n+k]时,包括[n:n+1],[n:n+2],[n:n+3]...[n:n+k]在内的所有子数组都满足要求。当前满足要求的数组个数为窗口右端点减去左端点再加一,因为当窗口大小为一时,两个数重合仍然有一个数满足要求。
实现代码如下
示例1:
输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc",所以其长度为3。示例2:
输入:s="bbbbb"输出:1解释:因为无重复字符的最长子串是"b",所以其长度为1。示例3:
输入:s="pwwkew"输出:3解释:因为无重复字符的最长子串是"wke",所以其长度为3。请注意,你的答案必须是子串的长度,"pwke"是一个子序列,不是子串。提示:
使用滑动窗口来记录当前无重复字符的子串。当新字符进入滑动窗口时,如果该字符已存在于窗口中,则从左侧开始移除字符,直到窗口中不再包含重复字符为止。