文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接:713. 乘积小于 K 的子数组
题单位置:
-
- 滑动窗口(定长/不定长/多指针)
- 不定长滑动窗口(求子数组个数)
2. 题目解析
经典的 双指针、滑动窗口 问题。
思路:
- 能发现让右边界向右拓展时,窗口内元素已经大于 k,则可以尝试缩小左边界。
- 且左边界不会再回头向左拓展,左指针具有单调性。适合使用滑动窗口来处理。
技巧:
- 灵神这里写了些特殊判断,k=0、1,然后就可以在 while 循环中不用去判断 l<=r 的这个情况。反例就是 [1,1,1], k=1 这种情况。
- 个人觉得还是判断一下比较好。更加直观。
- 有些判断可加可不加,把握好就行。
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {int n = nums.size();int res = 0, s = 1;for (int l = 0, r = 0; r < n; r ++ ) {s *= nums[r];while (l <= r && s >= k) s /= nums[l ++ ]; // 这样写,l 最终可能会越界,超过 rres += r - l + 1;}return res;}
};