ผลิตภัณฑ์ Subarray น้อยกว่า K ใน C++

สมมุติว่าเราให้อาร์เรย์จำนวนเต็มบวกจำนวนเต็ม เราต้องนับและพิมพ์จำนวนอาร์เรย์ย่อย (ต่อเนื่องกัน) โดยที่ผลคูณของแต่ละองค์ประกอบในอาร์เรย์ย่อยมีค่าน้อยกว่า k ดังนั้นหากอินพุตเป็น [10,5,2,6] และ k :=100 เอาต์พุตจะเป็น 8 ดังนั้นอาร์เรย์ย่อยจะเป็น [[10], [5], [2], [6], [10, 5], [5, 2], [2, 6] และ [5, 2, 6]]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• อุณหภูมิ :=1, j :=0 และ ans :=0
• สำหรับ i ในช่วง 0 ถึงขนาดของอาร์เรย์
  • อุณหภูมิ :=อุณหภูมิ * nums[i]
  • ในขณะที่อุณหภูมิ>=k และ j <=i ทำ
    • อุณหภูมิ :=อุณหภูมิ / nums[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

ผลลัพธ์

8