乘积小于 K 的子数组 - 滑动窗口

题目链接

乘积小于K的子数组

题目描述

解题思路

方法一：滑动窗口

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int len = nums.length;
        int result = 0;
        int cnt = 1;
        int startIdx = 0;
        for(int i=0; i<len; i++) {
            cnt *= nums[i];
            if(cnt < k) {
                result += (i - startIdx + 1);
            } else {
                for(;startIdx<i; ) {
                    cnt /= nums[startIdx++];
                    if(cnt < k) {
                        break;
                    }
                }
                if(cnt < k) {
                    result += (i - startIdx + 1);
                } 
            }
        }
        return result;
    }
}