从今日起在leetcode上进行每日一题的训练，接受坛友的监督，也欢迎各位大佬交流指导。
今日题目：
713. 乘积小于 K 的子数组
给你一个整数数组 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
题解
本题要求返回的是连续的相邻子数组, 第一个想到的就是滑动窗口, 设置窗口的前后指针, 当窗口内的积<k时, 扩大窗口, 并增加计数, 当窗口内的积≥k时, 缩小窗口, 直到重新满足<k的条件为止. 这里增加计数的地方需要仔细考量, 并不是扩大窗口且积<k时, 就将计数加一, 因为该题是求积, 所以当两个数的积<k时, 其实已经包含了每个数都小于k在其中, 同理, 当三个数积<k时, 包含了任意两个的组合积都<k, 而本题只要求连续相邻的子序列. 故每次窗口扩大且符合条件时增加的计数应该为当前窗口的长度. (可以自己考虑一下从2个数扩大到3个数时默认新增了几种符合要求的子序列, 应该是包含新增加的数本身, 加上相邻一个数, 加上相邻两个数三种情况, 前面两个数的情况在之前已经计数过了)
代码
func numSubarrayProductLessThanK(nums []int, k int) int {
front := 0
back := 0
sum := 1
result := 0
for front < len(nums){
sum *= nums[front]
if sum < k{
front++
result += front - back
}else{
if front == back{
front++
back++
sum = 1
continue
}
sum /= nums[back]
sum /= nums[front]
back++
}
}
return result
}
总结
在查看速度更快的题解代码时, 发现可以通过内层循环一直缩小窗口到<k时, 才继续向下滑动窗口, 这样外层只需要不断向下遍历来扩大窗口即可. 这样写循环思路更清晰, 代码更简洁 如下
func numSubarrayProductLessThanK(nums []int, k int) int {
if k <= 1 {
return 0
}
res := 0
p := 1
j := 0
for i := 0; i < len(nums); i++ {
p *= nums[i]
for p >= k {
p /= nums[j]
j++
}
res += i -j + 1
}
return res
}
想到这, 忽然明白, 其实核心在于只需要考虑以某个位置为结尾的向前连续符合要求的数组长度作为该位置处应该增加的计数数目即可. 这样就把整个问题拆分成了独立不关联的小问题. 将每个位置应该增加的计数数目累积, 就是最终的结果.
