題目描述:給定正整數陣列 nums 和整數 k,回傳乘積嚴格小於 k 的連續子陣列個數。
解題思路:使用滑動視窗。維護左指針 left、右指針 right 以及視窗內元素的乘積 product。右指針向右擴展時,將 nums[right] 乘入 product。每當 product >= k,就從左側收縮——將 product 除以 nums[left] 並右移 left——直到 product < k 或視窗為空。此時以 right 為右端點、left 為左端點的視窗合法,其中所有以 right 結尾的子陣列個數恰好為 right - left + 1(即 [left..right]、[left+1..right]、…、[right..right] 共 right - left + 1 個)。將此值累加到答案。邊界條件:若 k <= 1,因陣列元素均為正整數(至少為 1),乘積恆不小於 1,直接回傳 0。
時間複雜度:O(n) — right 和 left 各最多移動 n 次,每次乘除操作為 O(1),總計 O(n)。
空間複雜度:O(1) — 只使用常數個輔助變數。
1. If k <= 1, return 0.
2. Initialize left = 0, product = 1, count = 0.
3. For right from 0 to n-1:
a. Multiply product by nums[right].
b. While product >= k:
- Divide product by nums[left].
- Increment left.
c. Add (right - left + 1) to count.
4. Return count.方法一:滑動視窗(最優解) — 如本題解,時間 O(n)、空間 O(1)。利用「以 right 結尾的合法子陣列數 = right - left + 1」的計數技巧,一次掃描完成。
方法二:前綴積 + 二分搜尋 — 對乘積取對數,將乘積問題轉為前綴和問題(log(a×b) = log a + log b)。建立對數前綴和陣列後,對每個右端點二分搜尋最小左端點。時間 O(n log n)、空間 O(n)。需注意浮點精度問題。
方法三:暴力枚舉 — 雙重迴圈枚舉所有子陣列並計算乘積。時間 O(n²)、空間 O(1)。思路簡單,但 n = 3×10⁴ 時會超時。
right - left + 1 而非其他值?請用具體例子驗證這個計數公式的正確性。product /= nums[left] 的操作會遇到什麼問題?如何修改程式碼以正確處理含 0 的情況?