Subarray Product Less Than K ใน C++

โจทย์: Subarray Product Less Than K

ให้อาร์เรย์ของจำนวนเต็มบวก nums และค่า k ต้องนับจำนวน ซับอาร์เรย์ติดต่อกัน (contiguous subarrays) ที่ผลคูณขององค์ประกอบทุกตัวในซับอาร์เรอยาว น้อยกว่า k

ตัวอย่าง: nums = [10, 5, 2, 6], k = 100

ซับอาร์เรย์ที่ถูกต้อง 8 ชุด: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]

ผลลัพธ์: 8

อัลกอริทึม: Sliding Window (หน้าต่างเลื่อน)

1. กำหนด product = 1 (ผลคูณสะสม), left = 0 (ขอบซ้ายหน้าต่าง), ans = 0
2. วนลูป right จาก 0 ถึง n-1 (ขยายขอบขวา):
   • product *= nums[right]
   • ในขณะที่ product >= k และ left <= right (หน้าต่างกว้างเกิน/ผลคูณมากเกินไป):
     • product /= nums[left] (หดหน้าต่างจากซ้าย)
     • left++
   • ตอนนี้หน้าต่าง [left, right] มีผลคูณ < k แล้ว จำนวนซับอาร์เรย์ที่จบที่ right คือ right - left + 1
   • ans += right - left + 1
3. ส่งคืน ans

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0; // กรณีขอบ: k <= 1 ไม่มีซับอาร์เรย์ไหนผลคูณ < k (เพราะ nums[i] >= 1)
        
        long long product = 1; // ใช้ long long ป้องกัน overflow
        int left = 0;
        int ans = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            product *= nums[right];
            while (product >= k && left <= right) {
                product /= nums[left];
                left++;
            }
            ans += right - left + 1;
        }
        return ans;
    }
};

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

Input

[10,5,2,6] 100

Output

8

ความซับซ้อน (Complexity)

• เวลา: O(n) - แต่ละ index เข้าออกหน้าต่างได้สูงสุด 1 ครั้ง
• พื้นที่: O(1) - ใช้ตัวแปรคงที่

ข้อสังเกตสำคัญ: เนื่องจาก nums[i] เป็นจำนวนเต็มบวก ผลคูณจึงเพิ่มขึ้นอย่างเคร่งครัดเมื่อขยายหน้าต่าง และลดลงอย่างเคร่งครัดเมื่อหดหน้าต่าง ทำให้ Sliding Window ทำงานได้ถูกต้อง