LeetCode 713. 乘积小于 K 的子数组

713. 乘积小于 K 的子数组

【双指针】s表示前j到i的数字的乘积，当发现乘积大于等于k的时候，就把j向右移动，并且把s除掉个nums[j]，这样得到的就是以i结尾的符合要求的数组的最大长度，比这个长度小的以i结尾的也都符合要求，所以每次求完之后把答案加上这个区间长度即可。

class Solution {public int numSubarrayProductLessThanK(int[] nums, int k) {int acc = 1, n = nums.length, ans = 0;for (int i = 0, j = 0; i < n; i++) {acc *= nums[i];while (j <= i && acc >= k) acc /= nums[j++];if (acc < k) {ans += (i - j + 1);}}return ans;}
}

class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {int s = 1, n = nums.size(), ans = 0;for (int i = 0, j = 0; i < n; i++) {s *= nums[i];while (j <= i && s >= k) s /= nums[j++];if (s < k) ans += i - j + 1;}return ans;}
};