713. Subarray Product Less Than K 乘积小于 K 的子数组

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

@[toc]

题目地址: https://leetcode.com/problems/subarray-product-less-than-k/description/

题目描述

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Note:

• 0 < nums.length <= 50000.
• 0 < nums[i] < 1000.
• 0 <= k < 10^6.

题目大意

找出整数数组 nums 中，所有乘积小于 k的「连续子数组」。

注意，「子数组」是连续的，而「子序列」可以不连续。

解题方法

滑动窗口

本题关键点：

• 是求「子数组」，是连续的；
• 数组中所有数字均为正数；
• 只求个数，不用求出所有的结果。

上面的这三条，正是使用「滑动窗口」来解决的完美条件。

可以使用我多次分享的滑动窗口模板解决，模板在代码之后。

本题的滑动窗口定义：所有元素的乘积严格小于 $k$ 的连续子数组。

具体的做法：

1. 使用 $left$ 和 $right$ 两个指针，分别指向滑动窗口的左右边界。
2. 求窗口内所有的乘积，并判断：
   1. $right$ 主动右移：$right$ 指针每次移动一步：每次移动右指针之后，符合题目要求的结果增加的是此窗口内的子数组数量，也就是 $r-l+1$；
   2. $left$ 被动右移：如果乘积大于等于 $k$了，需要移动左指针。

可以完全套用本文的滑动窗口模板，根本不用思考。

Python 代码如下：

class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        N = len(nums) # 数组/字符串长度
        left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
        prods = 1 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数/乘积
        res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
        while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
            prods *= nums[right] # 增加当前右边指针的数字/字符的求和/计数
            while prods >= k and left <= right: # 此时需要一直移动左指针，直至找到一个符合题意的区间
                prods /= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
                left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
            # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
            res += right - left + 1 # 需要更新结果
            right += 1 # 移动右指针，去探索新的区间
        return res

C++ 代码如下：

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        const int N = nums.size();
        int left = 0;
        int right = 0;
        long long prods = 1;
        int res = 0;
        while (right < N) {
            prods *= nums[right];
            while (prods >= k && left <= right) {
                prods /= nums[left];
                left ++;
            }
            res += right - left + 1;
            right += 1;
        }
        return res;
    }
};

Java 代码如下：

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int N = nums.length;
        int left = 0;
        int right = 0;
        long prods = 1;
        int res = 0;
        while (right < N) {
            prods *= nums[right];
            while (prods >= k && left <= right) {
                prods /= nums[left];
                left ++;
            }
            res += right - left + 1;
            right += 1;
        }
        return res;
    }
}

复杂度

• 时间复杂度：$O(N)$
• 空间复杂度：$O(1)$

分享滑动窗口模板

《挑战程序设计竞赛》这本书中把滑动窗口叫做「尺取法」，我觉得非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动。

我分享一个滑动窗口的模板，能解决大多数的滑动窗口问题：

def findSubArray(nums):
    N = len(nums) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数/乘积
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
        while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
            sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
            left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
    return res

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：

1. 定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 sums 用来统计该区间内的各个字符出现次数；
2. 第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的求和/计数；
3. 第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left 每次移动到了新位置，需要减少 left 指针的求和/计数；
4. 在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，题目要求最大的区间长度，因此更新 res 为 max(res, 当前区间的长度) 。
5. right 指针每次向右移动一步，开始探索新的区间。

模板中的 sums 需要根据题目意思具体去修改，本题是求和题目因此把sums 定义成整数用于求和；如果是计数题目，就需要改成字典用于计数。当左右指针发生变化的时候，都需要更新 sums 。

另外一个需要根据题目去修改的是内层 while 循环的判断条件，即： 区间 $[left,right]$ 不符合题意 。

对于本题而言，就是该区间内的元素的乘积 大于等于了 $k$ 。

总结

1. 滑动窗口可以直接套模板，用我的这个模板，很简单

日期

2018 年 10 月 14 日 —— 周赛做出来3个题，开心 2022 年 5 月 5 日 —— 开始居家办公