信阳建设网站,软件开发工具分类,湖北省建设厅信息网站,wordpress收到登录错误题目
给定一个正整数数组 nums和整数 k #xff0c;请找出该数组内乘积小于 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]…题目
给定一个正整数数组 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 * 1041 nums[i] 10000 k 106 解题思路
前置知识 滑动窗口 1滑动窗口可以用以解决数组/字符串的子元素相关问题并且可以将嵌套的循环问题转换为单循环问题从而降低时间复杂度。故滑动窗口算法的复杂度一般为 O(n)。 2滑动窗口的基本思想如下 首先使用双指针维护一个子数组别称为 left 和 right。left 指向窗口的左端点right 指向窗口的右端点。如下图所示 窗口随着 right 指针向右滑动开始遍历整个数组区间即增大窗口 而在每次迭代内部即针对每一次 right要对子数组区间是否满足要求进行判断。如果子数组区间不能够满足条件则将 left 指针向右移动即缩小窗口这样窗口就实现了向右滑动。 知道了滑动窗口后我们来看一下这道题 1.题目要求我们求出 数组内乘积小于 k 的连续的子数组的个数一般求解子数组这类题我们都会用到滑动数组这道题也不例外 2.首先我们设置好要用到的变量curr 用来存放子数组的乘积sum 用来统计符合条件的子数组的个数i 作为滑动窗口中窗口的左边界。 3.我们for循环对数组进行遍历每当 j 遍历一个元素后就把它乘进 curr 中然后用while循环去判断这个滑动窗口内的乘积是否大于k若大于k 我们就将滑动窗口最左边的一个元素从curr中除去并将滑动窗口的左边界向右移动一个直到滑动窗口内的乘积小于k我们就把结果加到sum中注意这里的 right - left 1 就是以当前窗口右界为最后一个元素的连续子序列的个数。这么做的道理是这样的。如果一个长度为 n 的序列中的任意长度连续子序列都满足要求那么这些子序列可以无重复无遗漏地划分为 n 组组内子序列尾元素相同组间尾元素互异。 举个例子 思路: 设存在数组nums[A, B, C, D], k为乘积, count为符合条件的数组个数, i,j为窗口左右边界;*(假设) A: Ak ij0 -- count A (0-01)* B: ABk j1 -- count AB, B(1-01)* C: ABCk j2 -- BCk i1 -- count BC, C (2-11)* D: BCDk j3 -- CDK i2 -- D k i3 -- count D (3-31)* 当计算的数组乘积大于k时将窗口左边界右移, 直到小于k, 计算count窗口右边界右移* 当计算的数组乘积小于k时计算count窗口右边界右移* 得出规律每一次遍历count增加了j-i1 4.最后返回sum即可。 代码实现
class Solution {public int numSubarrayProductLessThanK(int[] nums, int k) {int n nums.length;int curr 1, sum 0, i 0; for(int j 0; j n; j){curr * nums[j];while(i j curr k ){curr / nums[i];i;}sum j - i 1;}return sum;}
}
测试结果 hh
