在本文中，我們將使用 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 函數小於給定範圍的下限。
該函數使用滑動視窗技術來尋找計數小於x 的子數組的計數.
首先，我們從「結束」和「開始」開始，其值均為0。當我們遍歷數組時，我們會維護從頭到尾的元素總和。之後，如果我們的開始等於結束並且總和大於或等於 x，我們開始移動開始並在從總和中取出元素時不斷減少總和。
直到我們的總和變得小於 x 或我們的開始變得大於結束。現在，我們將計數增加子數組計數，然後將右邊界增加 1。現在，在外循環結束後，我們傳回子數組的總計數。
在本文中，我們使用滑動視窗技術解決了一個問題，即在 O(n) 時間複雜度內找到總和在給定範圍內的子數組的數量。我們還從C 程式中學習了這個問題以及我們可以輕鬆解決這個問題的完整方法（正常且有效率）。我們可以用其他語言（例如 C、java、python 等）來寫相同的程式。
以上是使用C++編寫一個程式來找到具有給定範圍內和的子數組的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！
