C ++中子数组乘积小于K

假设我们给出了一个正整数nums的数组。我们必须计算并打印（连续）子数组的数量，其中子数组中每个元素的乘积小于k。因此，如果输入类似于[10,5,2,6]并且k：= 100，则输出将为8。因此，子数组将为[[10]，[5]，[2]，[6]， [10，5]，[5，2]，[2，6]和[5，2，6]]

为了解决这个问题，我们将遵循以下步骤-

• temp：= 1，j：= 0 and ans：= 0

• 对于范围在0到数组大小的i

• temp：= temp / nums [j]

• 将j增加1

• temp：= temp * nums [i]

• 当temp> = k且j <= i时

• ans：= ans +（i – j + 1）

• 返回ans

例子（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int numSubarrayProductLessThanK(vector<int>& nums, int k) {
      lli temp = 1;
      int j = 0;
      int ans = 0;
      for(int i = 0; i < nums.size(); i++){
         temp *= nums[i];
         while(temp >= k && j <= i) {
            temp /= nums[j];
            j++;
         }
         ans += (i - j + 1);
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {10,5,2,6};
   cout << (ob.numSubarrayProductLessThanK(v, 100));
}

输入项

[10,5,2,6]
100

输出结果

8