【Leetcode Daily】713乘积小于K的子数组

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个整数数组，求其中连续子数组之和小于 K 的个数。

思路分享

• 与之前越长越合法的题目稍有些不同，这时越短越合法，所以在之前的基础上（【Leetcode Daily】2962统计最大元素出现至少K次的子数组）略作修改。

• 无论是哪种类型，本质上都是遍历窗口的右端。以前是满足条件时不断向右滑窗口，直到滑不动时，记录当前窗口左侧加到结果上；而现在是满足条件时，要记录窗口内个数（right-left+1），因为窗口的左端在窗口内的任意一处必定满足条件。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;

        int left = 0, ans = 0;
        int cur = 1;
        for (int right = 0; right < nums.size(); right++) {
            cur *= nums[right];
            while (cur >= k) {
                cur /= nums[left++];
            }
            ans += right-left+1;
        }
        return ans;
    }
};