leetcode -滑动窗口

总结leetcode上滑动窗口类题目的做法

应用场景:

• 满足某种情况(计算结果, 出现次数, 同时包含)
• 最短/最长
• 子串/子数组/子序列

大致思路:

• 初始情况下, 左右边界处于数据最左侧, 窗口中没有内容
• 在条件不满足的时候拓宽右侧边界
• 在条件满足的时候收缩左侧边界, 更新最优解
• 时间复杂度为 O(n)

题目描述:
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目

解题步骤:

• 确认滑动窗口的左右边界left, right, 使用pro记录乘积, ret记录结果数量.
• 在边界范围中移动左右窗口, 并记录可能产生的子数组个数(具体看代码)
• 去除特殊情况, 当k<=1时

class Solution {
public:
    int numSubarrayProductLessThanK(vector& nums, int k) {
    	if(k<=1) return 0;
		int left = 0, right = 0;
		int pro = 1;
		int ret = 0;
		
		while(right < nums.size())
		{
			pro *= nums[right];	//乘积更新
			while(pro >= k)
			{
				pro /= nums[left];
				left++;	//当乘积大于k时, 除去左指针指向值
			}
			
			//*右指针每次移动, 记录可能产生的子数组个数* 
			ret += right - left + 1;
			right++;	
		}
		return ret;
    }
};

参考题解: 713.官方思路秒懂○注释详细○双指针滑窗 【附通用滑窗模板】