乘积小于K的子数组

1.静态滑动窗口

  1. 维护一个mul乘积 对乘积进行 * / 操作
  2. 当是当滑动窗口的长度len 非常大时， 乘积mul可能会超出数据范围 如果多个 0 ~ 1000 范围的num[i]相乘 可能超出 int 数据范围
  3. 这种方法非常容易超出int的数据范围 认定为失败的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) return 0;
        int ans = 0;
        //遍历滑动窗口的长度
        for (int len = 1; len <= nums.size(); ++len) {
            int mul = 1; int flag = 1;
            for (int i = 0; i < len; ++i) mul *= nums[i]; if (mul < k) ans++;
            for (int i = 1; i + len <= nums.size(); ++i) {
                mul /= nums[i - 1];
                mul *= nums[i + len - 1];
                if (mul < k) ans++;
            }
        }
        return ans;
    }
};

2.动态滑动窗口

  1. 从前往后处理所有的nums[i]，使用变量i、j代表窗口的左右端点（静态窗口弊端完美解决），使用变量mul记录当前窗口的乘积，
  2. 当 mul>=k 时，我们考虑将左端点i右移，同时消除左端点元素 nums[i] 对 mul 的贡献，直到mul>=k不再满足
  3. 这样就可以得到每个右端点 nums[i] 的最远左端点nums[j]，
  4. 进而得知以nums[i]为结尾（固定右端点）的合法子数组个数（左端点个数）为 i−j+1

image-20230427103411045

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;
        int ans = 0, mul = 1;
        //i 为左指针 j为右指针
        for (int i = 0, j = 0; j < nums.size(); ++j) {
            mul *= nums[j];
            while (mul >= k) { mul /= nums[i]; i++; }
            ans += j - i + 1;
        }
        return ans;
    }
};
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

3.前缀和+二分查找

前缀和+二分查找，

  1. 子数组元素乘积小于k即为 $\prod_{n = i}^{j}nums[n] < k$
  2. 由于在计算子数组乘积时会出现整型溢出的情况，可以将不等式两边取对数得到 $\prod_{n = i}^{j}log(nums[n]) < log(k)$
  3. 预处理出前缀和数组，
  4. 枚举子数组的右端点j ，在prefix数组的[0, j]区间中通过二分查找 寻找结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) return 0;
        int size = nums.size();

        //1.初始化前缀和数组 1 ~ len+1
        vector<double> prefix(size + 1);
        for (int i = 0; i < size; ++i) prefix[i + 1] = prefix[i] + log(nums[i]);
        
        //2.利用upper_bound进行查找
        double logk = log(k);
        int ans = 0;
        for (int j = 0; j < size; ++j) {
            //查找范围 prefix.begin() ~ prefix.begin() + high + 1
            //查找目标 prefix[high + 1] - log(k) + 1e-10 
            double temp = prefix[j + 1] - log(k) + 1e-10;
            int i = upper_bound(prefix.begin(), prefix.begin() + j + 1, temp) - prefix.begin();
            ans += j + 1 - i;
        }
        return ans;
    }
};
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$