1.题目
给你一个整数数组 nums 和一个整数 k ,请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
2.示例
示例 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 * 104
1 <= nums[i] <= 1000
0 <= k <= 106
3.思路
开始想的是遍历数组,以数组的每一个数开头向后遍历。计算乘积,当乘积不小于k了,再从下一个数字开始向后开始新一轮的遍历。这样可以得到所有的子数组,写完发现题目只要子数组的数量,然后这个方法不出意外的超时了。
官方的代码看不太明白,就用双指针的思路写了第二个方法,只需要理解:右指针每位移到一个新位置,应该加上 right - left + 1 种数组组合就好了。
4.代码
暴力
func numSubarrayProductLessThanK(nums []int, k int) int { //暴力 var ans []int var product int for i, _ := range nums { if nums[i] < k { temp := []int{nums[i]} ans = append(ans,temp) product = nums[i] for j := i+1; j < len(nums); j++{ product = product*nums[j] if product < k { temp = append(temp, nums[j]) log.Println(temp,nums[j]) ans = append(ans, temp) log.Println(ans) }else { break } } } } return len(ans) }
双指针
func numSubarrayProductLessThanK(nums []int, k int) int { //数组中数的范围是1~1000,所以当k=0时,没有满足要求的数组 if k == 0 { return 0 } //记录区间内的乘积 product := 1 var ans,left,right int //使右指针移动到右端则结束 for right < len(nums) { //记录乘积 product *= nums[right] //当前区间内的乘积大于等于k,左指针右移并把之前左指针的数除掉 for product >= k { product /= nums[left] left++ } //每次右指针位移到一个新位置,应该加上 right - left + 1 种数组组合: // nums[right] // nums[right-1], nums[right] // nums[right-2], nums[right-1], nums[right] // nums[left], ......, nums[right-2], nums[right-1], nums[right] //共有 right - left + 1 种 ans += right - left + 1 //右指针右移 right++ } return ans }