有关滑动窗口

261 字

1 分钟

有关滑动窗口

2022-05-09

刷题日常

算法

/

刷题

题目链接:https://leetcode-cn.com/problems/subarray-product-less-than-k/#

这道题其实自己开始能想到用双指针来做,

但是自己用一个窗口来维护乘积小于k,但是在计算满足条件的个数走了弯路,自己是在刚好不满足小于k的时候来计算cnt的,这时候要考虑是否有多计算的情况,其实在窗口移动的过程中,已经可以计算了.

自己的代码:

1
class Solution {
2
public:
3
    int numSubarrayProductLessThanK(vector& nums, int k) {
4
    int cnt=0;
5
    int l=0;
6
    int r=0;
7
    int lastr=-1;
8
    int sum=1;
9
    if(k==0)
10
    return 0;
11
    while(rl)
12
        cnt+=(r-l)*(r-l+1)/2;
13
        if (lastr>=l)
14
        cnt-=(lastr-l+2)*(lastr-l+1)/2;  //这里要减去重复的区间
15
        lastr=r-1;
16

17
        while(sum>=k)//这里要更新窗口左端点
18
        {
19
          sum/=nums[l];
20
          l++;
21
        }
22

23
        r++;
24
      }
25

26
    }
27

28
    if(r>l)
29
    cnt+=(r-l)*(r-l+1)/2;
30
    if (lastr>=l)
31
    cnt-=(lastr-l+2)*(lastr-l+1)/2;
32

33
    return cnt;
34

35
    }
36
};

官方题解:

1
class Solution {
2
public:
3
    int numSubarrayProductLessThanK(vector& nums, int k) {
4
        int n = nums.size(), ret = 0;
5
        int prod = 1, i = 0;
6
        for (int j = 0; j = k) {
7
                prod /= nums[i];
8
                i++;
9
            }
10
            ret += j - i + 1;//这里要明白这个等式是怎么来的,相当于固定了右端点.求子集个数.
11
        }
12
        return ret;
13
    }
14
};