Sản phẩm mảng con nhỏ hơn K trong C ++

Giả sử chúng ta đã cho một mảng số nguyên dương. Chúng ta phải đếm và in ra số mảng con (liền nhau) trong đó tích của mỗi phần tử trong mảng con nhỏ hơn k. Vì vậy, nếu đầu vào là [10,5,2,6] và k:=100, thì đầu ra sẽ là 8. Vì vậy, các mảng con sẽ là [[10], [5], [2], [6], [10, 5], [5, 2], [2, 6] và [5, 2, 6]]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• temp:=1, j:=0 và ans:=0
• cho tôi trong phạm vi từ 0 đến kích thước của mảng
  • temp:=temp * nums [i]
  • while temp> =k and j <=i, do
    • temp:=temp / nums [j]
    • tăng j lên 1
  • ans:=ans + (i - j + 1)
• trả lại ans

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[10,5,2,6]
100

Đầu ra

8