第11天(中等题 滑动窗口)

打卡第十一天
1道简单题+2道中等题

越短越合法型滑动窗口:

实例

• 由于子数组越长，乘积越大，越不能满足题目要求；反之，子数组越短，乘积越小，越能满足题目要求。有这种性质的题目，可以用滑动窗口解决。

• 内层循环结束后，[left,right] 这个子数组是满足题目要求的。由于子数组越短，越能满足题目要求，所以除了 [left,right]，还有 [left+1,right],[left+2,right],…,[right,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 left,left+1,left+2,…,right 的所有子数组都是满足要求的，这一共有 right−left+1 个，加到答案中: ans += right - left + 1;

代码:

class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {int n = nums.size();int left = 0,ans = 0,sum = 1;if(k <= 1){//所有数都是正整数,乘积不可能<1或0return 0;}for(int right = 0;right < n;right++){sum *= nums[right];while(sum >= k){sum /= nums[left];left++;}ans += right - left +1;//从left到right的所有子数组都满足条件,累加}return ans;}
};

耗时≈一小时 明天继续