713. 乘积小于 K 的子数组

这一题很像dp的思路，但是和求和最大的子数组又不太一样
用滑动窗口的思路不难，难点在于求数量这里，这个个数的求法很关键哈哈哈哈
image.png

  1. pub fn num_subarray_product_less_than_k(nums: Vec<i32>, k: i32) -> i32 {
  2.     let mut res = 0;
  3.     if k<=1 { return 0; }
  4.     // 用来记录滑动窗口内的值
  5.     let mut cur = 1;
  6.     let mut j = 0;
  7.     for i in 0..nums.len() {
  8.         cur *= nums[i];
  9.         while cur >= k {
  10.             cur /= nums[j];
  11.             j += 1;
  12.         }
  13.         res += i - j + 1;
  14.     }
  15.     res as i32
  16. }

下面有一种迭代器fold写法：

  1. impl Solution {
  2.     pub fn num_subarray_product_less_than_k(nums: Vec<i32>, k: i32) -> i32 {
  3.         if k <= 1 {
  4.             return 0;
  5.         }
  7.         (0..nums.len()).fold((0, 0, 1), |(ans, mut l, mut prod), r| {
  8.             prod *= nums[r];
  9.             while prod >= k {
  10.                 prod /= nums[l];
  11.                 l += 1;
  12.             }
  14.             (ans + r - l + 1, l, prod)
  15.         }).0 as i32
  16.     }
  17. }