题目内容

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2：

输入：nums = [1,2,3], k = 0
输出：0

提示:

• 1 <= nums.length <= 3 * 104
• 1 <= nums[i] <= 1000
• 0 <= k <= 106

解题思路

方法一

两层循环暴力搜索，时间复杂度O(n²)。

public int numSubarrayProductLessThanK(int[] nums, int k) {
        int sum = 1;
        int count = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                sum *= nums[j];
                if (sum >= k) break;
                count++;
            }
            sum = 1;
        }
        return count;
    }

运行结果

方法二

双指针滑动窗口，定义两个指针left和right，分别表示左右边界，让左右边界内的数组乘积始终小于K，统计数组的个数。循环开始时，先移动right指针，右指针加1表示增加了一个新的元素形成了一个新的数组，此时判断数组内的乘积是否大于等于K，如果乘积大于等于K，则停止移动右指针开始移动左指针，并且每一次都让乘积➗左指针指向的元素，直到乘积小于K时，停止移动左指针，继续移动右指针；在移动右指针的过程中，每次移动后如果数组乘积小于K，则相对于移动之前，增加的数组的数量是 right ➖ left ➕ 1 ，把每次移动右指针时满足条件的数组数量累加起来就是最终结果。

public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }
        int sum = 1;
        int count = 0;
        int left = 0, right = 0;
        while (right < nums.length) {
            sum *= nums[right];
            while (sum >= k) {
                sum /= nums[left++];
            }
            count += right - left + 1;
            right++;
        }
        return count;
    }

运行结果