713. Subarray Product Less Than K - Medium

前往題目

想法

• 用標準的Sliding window會漏掉幾個沒算到

思路

關鍵點只有在update的時候要取window size，這樣才是當前這個window的subarray總數

例如[5, 2, 6]，window size是3，也代表他有三個subarray -> [5], [5, 2], [5, 2, 6]

1. 標準sliding window，左右指針
2. 每次循環更新當前product
3. 將invalid變為valid
4. 加入window size到結果中

Code

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int l = 0;
        int res = 0;
        int curPro = 1;
        for (int r = 0; r < nums.length; ++r) {
            curPro *= nums[r];

            // Invalid, make it valid
            while (l <= r && curPro >= k) {
                curPro /= nums[l];
                ++l;
            }

            // Update subarrays count
            res += r - l + 1;
        }

        return res;
    }
}