发表于 2024.04.18

• 使用一个滑动窗口维护当前乘积小于k的最长连续子数组。每当窗口右侧向右扩展一个元素时，结果(有效子数组数量)加上新窗口的长度(即，新增了以窗口当前右侧元素结尾的长度为1,2,…,滑动窗口大小的数组)。当窗口无法向右扩展时，则左侧边界向右移动以减少乘积，直到下一次尝试向右扩展成功。

  class Solution:
      def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
          if k == 0:
              return 0
          result = 0
          # 窗口的边界
          left = 0  # 左侧包含
          right = 0  # 右侧不包含
          window_product = 1  # 空窗口的乘积设为1, 以方便乘
  
          while right < len(nums):
              if window_product * nums[right] < k:  # 尝试扩展右边界
                  result += right - left + 1
                  window_product *= nums[right]
                  right += 1
              else:  # 否则, 收缩左边界
                  window_product //= nums[left]
                  left += 1
                  if right < left:  # 如果窗口已经为空, 需要同步移动右边界, 并将窗口乘积重置为1
                      right = left
                      window_product = 1
          return result

• LC 题目链接