Java实现 LeetCode 713 乘积小于K的子数组（子集数量+双指针）

待我称王封你为后i 2023-07-23 14:00 8阅读 0赞

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

给定一个正整数数组 nums。

找出该数组内乘积小于 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的子数组。  
说明:

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

## `如果一个子串的乘积小于k，那么他的每个子集都小于k，而一个长度为n的数组，他的所有连续子串数量是1+2+...n，但是会和前面的重复。 比如例子中[10, 5, 2, 6]，第一个满足条件的子串是[10]，第二个满足的是[10, 5]，但是第二个数组的子集[10]和前面的已经重复了，因此我们只需要计算包含最右边的数字的子串数量，就不会重复了，也就是在计算[10, 5]这个数组的子串是，只加入[5]和[10, 5]，而不加入[10]，这部分的子串数量刚好是r - l + 1` ##

class Solution { 
          public int numSubarrayProductLessThanK(int[] nums, int k) { 
            int len;
            if (nums == null || (len = nums.length) == 0 || k <= 1) { 
                return 0;
            }
    
            int count = 0;
            int prod = 1;
            int left = 0;
            for (int right = 0; right < len; right++) { 
                // 如果正整数大于 1，才计算乘积.因为等于1的结果相乘始终等于之前的值，没必要再相乘了.
                // 如果正整数大于等于 k，与它相关的任何乘积，必然都大于等于 k，直接跳过
                int num = nums[right];
                if (num > 1) { 
                    if (num >= k) { 
                        left = right + 1;
                        prod = 1;
                        continue;
                    } else { 
                        prod *= num;
                        while (prod >= k) { 
                            prod /= nums[left++];
                        }
                    }
                }
                count += right - left + 1;
            }
            return count;
        }
    }