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

本文主要是介绍《剑指 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。

这篇关于《剑指 Offer》专项突破版 - 面试题 9 : 乘积小于 k 的子数组（相向双指针 C++ 实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---