leetcode 713. 乘积小于 K 的子数组

南鱼座α 199 2022-05-09

题目内容

给你一个整数数组 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(n2)。

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;
    }

运行结果

image-1652109125202

方法二

双指针滑动窗口,定义两个指针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;
    }

运行结果

image-1652109913524


# LeetCode # Medium # 滑动窗口