資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告