使用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 是陣列的大小。

我們'將使用滑動視窗方法尋找替代解決方案（這將幫助我們降低程式的時間複雜度）。

高效方法

與暴力破解不同

高效方法

strong>，我們不會遍歷所有子陣列。相反，只有當子數組的總和超過 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。隨著我們的處理進一步進行，它遍歷了其他可能形成的子數組。這些新的子數組的總和小於k被加到我們的答案中，因此我們的答案遞增。

與先前的暴力解法相比，這種方法非常高效，因為它的時間複雜度為O(N)，其中N是我們陣列的大小。

結論

在本文中，我們使用滑動視窗技術解決了一個問題，即找到和小於k的子數組的數量。我們也學習了這個問題的C 程序以及我們解決這個問題的完整方法（普通和高效）。我們可以使用其他語言（如C、Java、Python和其他語言）編寫相同的程式。希望您會發現本文有幫助。

以上是使用C++編寫，找到和小於K的子數組的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！