C++에서 K보다 작은 부분배열 곱

양의 정수 배열을 제공했다고 가정합니다. 하위 배열에 있는 각 요소의 곱이 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
0 범위에서 배열 크기까지의 i에 대해
- temp :=temp * nums[i]
- 동안 임시로>=k 및 j <=i, do
  - temp :=임시 / 숫자[j]
  - j를 1 증가
- ans :=ans + (i – j + 1)
반환

예시(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