《剑指 Offer》专项突破版 - 面试题 9 : 乘积小于 k 的子数组（相向双指针 C++ 实现）

题目链接：LCR 009. 乘积小于 K 的子数组 - 力扣（LeetCode）

题目：

输入一个由正整数组成的数组和一个正整数 k，请问数组中有多少个数字乘积小于 k 的连续子数组？例如，输入数组 [10, 5, 2, 6]，k 的值为 100，有 8 个子数组的所有数字的乘积小于 100，它们分别是 [10]、[5]、[2]、[6]、[10, 5]、[5, 2]、[2, 6]、[5, 2, 6]。

分析：

代码实现：

class Solution {
public:
 ? ?int numSubarrayProductLessThanK(vector<int>& nums, int k) {
 ? ? ? ?int n = nums.size();
 ? ? ? ?int product = 1;
 ? ? ? ?int count = 0;
 ? ? ? ?int left = 0;
 ? ? ? ?for (int right = 0; right < n; ++right)
 ? ? ?  {
 ? ? ? ? ? ?product *= nums[right];
 ? ? ? ? ? ?while (left <= right && product >= k)
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?product /= nums[left];
 ? ? ? ? ? ? ? ?++left;
 ? ? ? ? ?  }
 ? ? ? ? ? ?count += right - left + 1;
 ? ? ?  }
 ? ? ? ?return count;
 ?  }
};

注意：当 k == 1，且输入数组为只有一个数时，会越界访问 nums[left]，所以在 while 循环中需要添加条件： left <= right。