動機

right-left + 1等於以right為最後一個的array到left之間的所有array的組合數

這題要知道這個魔法才能做

Problem

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.

 

Example 1:

Input: nums = [10,5,2,6], k = 100Output: 8Explanation: 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 = 0Output: 0

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 106

Sol

left = 0
right = 3

[0,1,2,3]
[1,2,3]
[2,3]
[3]

OR

[0]
[0,1]
[0,1,2]
[0,1,2,3]
right-left+1 = 4

可以用right-left+1算一right為終點的組合數 只要知道這個魔法，就可以只靠index求組合數

這是從終點做

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # right-left + 1
        if k <= 1:
            return 0
        else:
            l, mul, ret = 0, 1, 0
            for r in range(len(nums)):
                mul *= nums[r]
                while mul >= k:
                    l, mul = l+1, mul // nums[l]
                ret += (r-l)+1
            return ret

從起點做

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # right-left + 1
        if k <= 1:
            return 0
        else:
            l,r, mul, ret = 0,1, nums[0], 0
            while l < len(nums):
                while r < len(nums) and nums[r]*mul < k:
                    mul *= nums[r]
                    r += 1
                ret += (r-l)
                
                mul, l = mul//nums[l], l+1
            return ret