数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中小于 K 的子数组乘积
假设我们给定了一个正整数数组 nums。我们必须计算并打印出 (连续) 子数组的数量，其中每个子数组中元素的乘积都小于 k。因此，如果输入类似于 [10, 5, 2, 6] 且 k := 100，则输出将为 8。因此，子数组将为 [[10], [5], [2], [6], [10, 5], [5, 2], [2, 6] 和 [5, 2, 6]]
为了解决这个问题，我们将遵循以下步骤 -
- temp := 1，j := 0 且 ans := 0
- 对于 i 的范围从 0 到数组的大小
- temp := temp * nums[i]
- 当 temp >= k 且 j <= i 时，执行
- temp := temp / nums[j]
- 将 j 增加 1
- ans := ans + (i – j + 1)
- 返回 ans
示例（C++）
让我们看看以下实现，以便更好地理解 -
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
lli temp = 1;
int j = 0;
int ans = 0;
for(int i = 0; i < nums.size(); i++){
temp *= nums[i];
while(temp >= k && j <= i) {
temp /= nums[j];
j++;
}
ans += (i - j + 1);
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {10,5,2,6};
cout << (ob.numSubarrayProductLessThanK(v, 100));
}输入
[10,5,2,6] 100
输出
8
更新于: 2020-04-29
303 次查看
广告