给定一个长度为 n 的正整数数组 nums , 请你找出这个数组中乘积小于 k 的连续子数组的个数。
数据范围: , 数组中的值满足 ,
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param k int整型 * @return int整型 */ int subarrayCnt(vector<int>& nums, int k) { // write code here int left=0, right=0, result=0, sum=1; for(int right=0;right<nums.size();right++) { sum*=nums[right]; while(left<=right&&sum>=k) { sum/=nums[left]; left++; } result+=right-left+1; } return result; } };
package main import _"fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param k int整型 * @return int整型 */ func subarrayCnt( nums []int , k int ) int { ans:=0 for i:=0;i<len(nums);i++{ tot:=1 for j:=i;j<len(nums);j++{ tot*=nums[j] if tot<k{ ans++ }else{ break } } } return ans }
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @param k int整型 # @return int整型 # class Solution: """ 题目: https://www.nowcoder.com/practice/3835601459064f52b154d2d0ab04087b?tpId=196&tqId=40555&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title= 算法: 本题的关键在于两点:1)子数组的枚举 2)计算子数组的乘积 这里我们使用双指针i, j,指针i枚举子数组左边界,指针j枚举右边界,mulNum记录当前区间的乘积,当mulNum小于k时,计数+1,否则i右移,重置j与mulNum 复杂度: 时间复杂度:O(n^2) 空间复杂度:O(1) """ def subarrayCnt(self, nums, k): # write code here n, count = len(nums), 0 for i in range(n): j, mulNum = i, 1 while j < n: mulNum *= nums[j] if mulNum >= k: break count += 1 j += 1 return count if __name__ == "__main__": sol = Solution() # nums, k = [10, 5, 3, 7], 100 nums, k = [10, 5, 3, 7], 0 res = sol.subarrayCnt(nums, k) print res