LCR.P9[乘积小于K的子数组]

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int n = nums.length, prod = 1, ans = 0;
        for (int left = 0, right = 0; right < n; ++right) {
            prod *= nums[right];
            while (prod >= k) prod /= nums[left++];
            ans += right - left + 1;
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$