LeetCode 713. 乘积小于K的子数组

发表于 更新于 分类于 Changyan： 本文字数： 283 阅读时长 ≈ 1 分钟

题目描述

乘积小于K的子数组

给定一个正整数数组 nums ，找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:

输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

解题思路（滑动窗口）

采用滑动窗口的方法，先设置left初始值为0，然后循环增加right的值，乘积（滑动窗口）乘以 nums[right]，单调不减，直到乘积 >= k；再将left向右移动，乘积除以 nums[right]，单调不增，直到乘积 < k。算法时间复杂度为O(n)。

题目难点在于，当right增长时如何计数，计数代码为：

1
ans += right - left + 1

具体为什么这样计算，参照累加和公式：

$\sum_1^n x = n + \sum_1^{n-1} x$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
  int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1)
      return 0;
    int product = 1, ans = 0, left = 0;
    for (int right = 0; right < nums.size(); right++) {
      product *= nums[right];
      while (product >= k) {
        product /= nums[left];
        left++;
      }
      ans += right - left + 1;
    }
    return ans;
  }
};