題目網址：https://leetcode.cn/problems/subarray-product-less-than-k/

題意：給一整數 array nums 和一整數 k, 返回所有 subarray 中所有乘積小於 k 的連續 subarray 個數。

Solution：

想法：利用 Two Pointers + Sliding Window

  • 用 prod 紀錄 left ~ right 之連續數乘積
  • 若 prod > k : 則 prod /= nums[left], 且 left 要不斷右移, 直到 prod < k
  • 新增的連續 subarray 總共有 right - left + 1 個（以 right 為結尾的連續 subarray）
    e.g. nums = [10, 5, 2, 6], k = 100
    • left = 0 = right, 取 10 < 100 ➔ res = 1
    • left = 0, right = 1, 取 10 * 5 < 100 ➔ res = 1 + 2 = 3
      因為除了原本的 [10] 之外新增了 [5], [10, 5] 這兩個以 5 為結尾的連續 subarray
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        const int n = nums.size();
        int left = 0, res = 0, prod = 1;

        for (int right = 0; right < n; ++right) {
            prod *= nums[right];
            while (left <= right && prod >= k) {
                prod /= nums[left++];
            }
            res += right - left + 1; // 因為是連續 subarray
        }

        return res;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 撇除要返回的 res, 只需常數空間