資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 查詢給定範圍內的子陣列數量
在本文中，我們將使用 C++ 程式解決在給定範圍內求和的子陣列數量的問題。我們有一個正整數陣列 arr[]，以及一個範圍 {L, R}，我們需要計算在給定範圍 L 到 R 內求和的所有子陣列的總數。以下是一個簡單的示例問題：
Input : arr[] = {1, 4, 6}, L = 3, R = 8
Output : 3
The subarrays are {1, 4}, {4}, {6}.
Input : arr[] = {2, 3, 5, 8}, L = 4, R = 13
Output : 6
The subarrays are {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8}.查詢解決方案的方法
我們將解釋兩種使用 C++ 解決此問題的方法：
暴力方法
最基本的暴力方法用於計算每個子陣列的和，然後查詢該和是否存在於給定範圍內。（但是這種方法會花費我們大量時間，因為它的時間複雜度為 O(n*n)，其中 n 是陣列的大小）。
高效方法
為了節省時間，我們使用另一種稱為高效方法的方法。現在，高效方法使用滑動視窗技術，使用這種技術，我們將以 O(n) 的效率更快或更有效地計算結果。
示例
#include <bits/stdc++.h>
using namespace std;
int subCount(int *arr, int n, int x){
int start = 0, end = 0, sum = 0, count = 0;
while (end < n){ // we will be moving right border in this loop
sum = sum + arr[end];
while(start <= end && sum >= x){ // this loop will move our left border
sum = sum - arr[start]; // we will decrement sum while moving left border.
// For excluding the previous elements.
start++; // and move the left border.
}
count = count + ((end - start) + 1); // counting the subarrays.
end++;
}
return count;
}
int main(){
int n; // size of array
int L, R;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];
cin >> L >> R;
int answer;
answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // Final Answer.
cout << answer << "\n";
return 0;
}輸出
1
以上程式碼的解釋
在這種方法中，我們計算和小於給定範圍上限的子陣列的數量，然後使用我們的 subcount 函式減去和小於給定範圍下限的子陣列的數量。
Subcount 函式
此函式使用滑動視窗技術查詢計數小於 x 的子陣列的計數。
首先，我們將“end 和 start”都設定為 0 作為其值。當我們遍歷陣列時，我們保持從開始到結束的元素的總和。之後，如果我們的 start 等於我們的 end 且總和大於或等於 x，我們開始移動我們的 start 並隨著我們從總和中移除元素而減少我們的總和。
直到我們的總和變小於 x 或我們的 start 變大於 end。現在，我們透過子陣列計數增加計數，然後將右邊界增加 1。現在，在我們的外部迴圈結束後，我們返回子陣列的總計數。
結論
在本文中，我們解決了一個問題，即使用滑動視窗技術以 O(n) 的時間複雜度查詢給定範圍內的子陣列數量。我們還從解決此問題的 C++ 程式以及我們可以輕鬆解決此問題的完整方法（普通方法和高效方法）中學到了知識。我們可以在其他語言（如 C、Java、Python 等）中編寫相同的程式。
853 次瀏覽
