資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 查詢和小於 K 的子陣列數量
在本文中，我們將使用 C++ 找出和小於 K 的子陣列的數量。在這個問題中，我們有一個數組 arr[] 和一個整數 K。所以現在我們必須找到總和小於 K 的子陣列。這是一個例子 -
Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3}查詢解決方案的方法
現在我們將使用兩種不同的方法來解決給定的問題 -
暴力法
在這種方法中，我們將遍歷所有子陣列並計算它們的和，並與 k 進行比較，如果和小於 k 則增加我們的答案。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
for(int i = 0; i < size; i++){ // outer loop.
int sum = 0;
for(int j = i; j < size; j++){ // inner loop.
sum = sum + arr[j];
if(sum < k) // comparing with k.
ans++; // incrementing our ans if sum is less than k.
}
}
cout << ans << "\n";
return 0;
}輸出
4
但是，這種方法不是很好，因為它的時間複雜度非常高 **O(N*N)**，其中 n 是我們陣列的大小。
我們將研究使用滑動視窗方法的替代解決方案（這將有助於我們降低程式的時間複雜度）。
高效方法
與 **暴力法** 不同，我們不會遍歷所有子陣列。相反，我們只會在子陣列的和超過 k 時遍歷，並將我們的左邊界移動到我們的右邊界，並重復此操作，直到遍歷整個陣列。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
int start = 0; // left border.
int end = 0; // right border.
int sum = 0;
while(end < size && start < size){ // till the whole array is traversed.
while(sum >= k && start < end){
sum = sum - arr[start];
start++;
}
if(end >= start)
ans = ans + end - start;
sum += arr[end];
end++;
}
cout << ans << "\n";
return 0;
}輸出
4
在這種方法中，我們使用 **滑動視窗技術** 使我們的程式執行得更快或更有效率，以便在更大的約束條件下執行。
以上程式碼的解釋
在這種方法中，我們通常遍歷直到我們的和小於 k 並根據它增加我們的答案，現在程式碼中發生的重大變化是在和變得大於或等於 k 時。在這種情況下，我們開始將我們的左邊界增加到小於我們的右邊界或直到和大於或等於 k。隨著我們進一步處理，它遍歷可以形成的其他子陣列。這些總和小於 k 的新子陣列被新增到我們的答案中，因此我們的答案被增加。
與我們之前應用的 **暴力法** 相比，這種方法非常有效，因為它的時間複雜度為 **O(N)**，其中 N 是我們陣列的大小。
結論
在本文中，我們解決了一個問題，即使用 **滑動視窗技術** 查詢和小於 k 的子陣列的數量。我們還學習了這個問題的 C++ 程式以及我們解決此問題的完整方法（普通方法和高效方法）。我們可以用其他語言（如 C、Java、Python 和其他語言）編寫相同的程式。希望本文對您有所幫助。
964 次檢視
