image.png

思路：滑动窗口

  • 此题基于一个主要的前提，这是思考的关键。对于符合条件的某个子区间而言，固定住其右边界right，一共有right - left + 1个子数组满足条件。

[left, right] [left + 1,right] … [left + (right - left), right] 一共 right - left + 1个子数组满足条件

  • 而滑动窗口，或者双指针的大前提，就是保证有序性。可以采用滑动窗口的方法，逐个确定以right为边界的子数组的个数。

代码：

  1. class Solution {
  2. public:
  3.     int numSubarrayProductLessThanK(vector<int>& nums, int k) {
  4.         if (k == 0 || k == 1) return 0;
  5.         int count_sub = 0, len_nums = nums.size();
  6.         if (!len_nums) return 0;
  7.         int cur_product = 1;
  9.         for (int left = 0, right = 0; right < len_nums; ++right) {
  10.             cur_product *= nums[right];
  11.             while (cur_product >= k) {
  12.                 cur_product /= nums[left++];
  13.             }
  14.             // [left, right], [left + 1, right] ... [left + (right - left), right]
  15.             // 对特定的right而言，有right - left + 1 个子数组符合条件，这是理解的关键
  16.             count_sub += right - left + 1;
  17.         }
  19.         return count_sub;
  20.     }
  21. };