資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
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 arr[] = { 1, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int L = 3;
int R = 8;
int answer;
answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // Final Answer.
cout << answer << "\n";
return 0;
}輸出
3
以上程式碼的解釋
在這種方法中，我們計算和小於給定範圍上限的子陣列數量，然後我們使用我們的subcount函式減去和小於給定範圍下限的子陣列數量。
Subcount函式
此函式使用滑動視窗技術來查詢計數小於x的子陣列的計數。
首先，我們將'end'和'start'都設定為0。當我們遍歷陣列時，我們保持從start到end的元素的和。之後，如果我們的start等於我們的end並且sum大於或等於x，我們開始移動我們的start並隨著我們從sum中移除元素而減少我們的sum。
直到我們的sum小於x或我們的start大於end。現在我們用子陣列計數增加計數，然後將右邊界加1。現在，在我們的外迴圈結束之後，我們返回子陣列的總計數。
結論
在本文中，我們使用滑動視窗技術，以O(n)的時間複雜度解決了查詢和在給定範圍內的子陣列數量的問題。我們還學習了C++程式以及解決這個問題的完整方法（普通方法和高效方法），我們可以輕鬆地解決這個問題。我們可以使用其他語言（例如C、Java、Python等）編寫相同的程式。
更新於：2021年11月25日
248 次瀏覽
廣告