【leetcode】713.Subarray-Product-Less-Than-K.md

题目

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

分析

给定一个正整数组，和一个整数k，求成绩小于k的连续子数组个数

这道题真的是做了很久，想到了用滑窗，用一个数字记录窗口内数字成绩，但是算不明白个数

问题的关键在于:

每次滑窗的末尾向后移动一位之后，满足条件的窗口内新增的连续子数组数目为：end-start+1

因为每次滑窗末尾向后移动一位，新增的子数组必然包含最后一个数字，又必须是连续子数组，所以新增的个数是end-start+1

代码

最后附上很简单的代码

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    int product = 1;
    int count = 0;
    int start = 0;
    int end = 0;
    while(end < nums.size()&&start<=end){
        product = product*nums[end];
        while(product>=k&&start<=end){
            product = product/nums[start];
            start++;
        }
        count+=end-start+1;
        end++;
    }
    return count;
}