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 且 ans := 0
  • 对于 i 的范围从 0 到数组的大小
    • temp := temp * nums[i]
    • 当 temp >= k 且 j <= i 时，执行
      • temp := temp / nums[j]
      • 将 j 增加 1
    • 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

更新于: 2020-04-29

303 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告