LeetCode 练习——713. 乘积小于 K 的子数组
1.题目描述
给你一个整数数组 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输出：02.解题思路与代码
2.1 解题思路
这道题需要求满足乘积小于 k 的连续子数组，那么可以考虑使用滑动窗口的方式进行解答。开始的时候 right 先移动。当 left 到 right 之间数字乘积小于 k 时，统计 left 和 right 之间个数；当 left 到 right 之间数字乘积大于等于 k 时，right 停住，移动 left ，直到 left 到 right 之间乘积小于 k 为止，统计 left 到 right 之间数字个数即可。以 [10, 5, 2, 6] ，k 取100为例：
-
left 、right 从 0 开始，此时 tmp 等于 10 ，小于 k ，统计 left 和 right 之间个数，此时 ans 为 1；
-
right 继续前进，right=1 ，tmp 等于 50 ，小于 k ，继续统计个数并累加上 ans，此时 ans 为 3；
-
right 继续前进，right=2 ，tmp 等于 100，等于 k，不满足要求开始移动 left；
-
left 前进一位， tmp 等于 10，小于 k，统计 left 和 right 之间个数为 2，此时 ans 累加为 5；
-
right 继续前进，tmp 等于 60，小于 k，统计 left 和 right 之间个数为 3，此时 ans 累加为 8；
-
right 继续前进，此时 right 超出边界，循环结束，得到答案 ans=8。
2.2 代码
class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { if (k <= 1) { return 0; } int tmp = 1; int left = 0; int right = 0; int ans = 0; while (right < nums.length) { tmp *= nums[right]; while (tmp >= k) { tmp /= nums[left]; left++; } ans += right - left + 1; right++; } return ans; }}2.3 测试结果
通过测试
3.总结
- 这道题属于滑动窗口的简单应用，想到这一点解题就不算太难
- 先移动右指针，满足条件统计一次，当不满足条件时，移动左指针直到满足条件为止