leetcode -滑动窗口_C

前言

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

应用场景:

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

大致思路:

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

713. 乘积小于 K 的子数组

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

解题步骤:

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

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& 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;
    }
};