【力扣打卡系列】滑动窗口与双指针(乘积小于K的子数组)
坚持按题型打卡&刷&梳理力扣算法题系列，语言为go，Day6
乘积小于K的子数组
- 题目描述
- 解题思路
- 双指针移动，遍历右端点right，滑动左端点left
- 子数组的个数：固定右端点r，子数组的个数其实就是从l到r的元素的个数，即r-l+1
- 反向控制条件for sum >= k{}，当sum<k，即满足操作时，执行ans += right-left +1
- 代码参考
func numSubarrayProductLessThanK(nums []int, k int) int {
left := 0
sum := 1
ans := 0
if k <= 1 {
return 0
}
for right,value :=range nums{
sum *= value
for sum >= k{
sum /= nums[left]
left++
}
ans += right-left +1
}
return ans
}
- tips
- 双指针的应用场景
- 指针移动的过程中，sum和是在不断变小的，while条件逐渐从满足要求变为不满足要求，这就是单调性，只有满足单调性才可以使用双指针
- 子数组的个数：固定右端点r，子数组的个数其实就是从l到r的元素的个数，即r-l+1
- 即[l,r]满足要求的话，[l,r],[l+1,r]…[r,r]都是满足要求的（固定右端点）