[Leetcode] Subarray Product Less Than K

Contiguous elements within array varying self length -> sliding window .

Description

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Examples

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.

Example 2:

Input: nums = [1,2,3], k = 0
Output: 0

Solution

template

The tricky part is how to update res.

The number of possible combination of [x1, x2,…,xn] = 1 + 2 + … + n, same as suming up the len whenever array has been altered. e.g. [10,5,2,6] poosiblem subarrays [10] -> [5] [10, 5] -> [2] [5, 2] [10, 5, 2] -> [6] [2, 6] [5, 2, 6] [10, 5, 2, 6] From example we see when subarray changes, the number of new combination equals to len of curr subarray.

Therefore, in each round of loop, increments curr length to the kept global variable.

• code

ref: https://maxming0.github.io/2020/09/28/Subarray-Product-Less-Than-K/