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

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们给出了一个正整数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

    以上是 C ++中子数组乘积小于K 的全部内容， 来源链接： utcz.com/z/316711.html

    回到顶部