Subarray Product Less Than K trong C++

Cho mảng số nguyên dương nums và số k. Đếm số subarray liên tiếp mà tích các phần tử nhỏ hơn k.

Ví dụ: nums = [10,5,2,6], k = 100 → output 8. Các subarray: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6].

Giải thuật (Cửa sổ trượt)

• temp = 1, j = 0, ans = 0.
• Duyệt i từ 0 đến n-1:
  • temp *= nums[i]
  • Khi temp >= k và j <= i: temp /= nums[j], j++.
  • ans += i - j + 1.
• Trả về ans.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        lli temp = 1;
        int j = 0, 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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {10,5,2,6};
    cout << ob.numSubarrayProductLessThanK(v, 100);
    return 0;
}

Input

[10,5,2,6] 100

Output

8