Ditulis dalam C++, cari bilangan subarray yang jumlahnya kurang daripada K

Dalam siaran ini, kita akan mendapati bilangan subarray dengan jumlah kurang daripada K menggunakan C++. Dalam masalah ini, kita mempunyai array arr[] dan integer K. Sekarang kita perlu mencari subarray yang jumlahnya kurang daripada K. Di bawah ialah contoh −

Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3}

Cara untuk mencari penyelesaian

Sekarang kita akan menggunakan dua kaedah yang berbeza untuk menyelesaikan masalah yang diberikan -

Brute force

Dalam kaedah ini kita akan mengulangi semua sub tatasusunan dan Kira jumlahnya dan jika jumlahnya kurang daripada k, bandingkan dengan k untuk menambah jawapan kita.

Contoh

#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;
}

Output

4

Walau bagaimanapun, kaedah ini tidak begitu baik kerana kerumitan masanya sangat tinggi O(N*N), di mana n ialah saiz array.

Kami akan mencari penyelesaian alternatif menggunakan pendekatan tetingkap gelongsor (ini akan membantu kami mengurangkan kerumitan masa program).

Kaedah cekap

Tidak seperti brute force

kaedah cekap

kuat>, kami tidak mengulangi semua sub-array. Sebaliknya, hanya apabila jumlah subarray melebihi k , kami mengulang dan mengalihkan sempadan kiri ke sempadan kanan dan mengulangi sehingga keseluruhan tatasusunan dilalui.

Contoh

#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;
}

Output

4

Kami menggunakan Teknik Tingkap Gelongsor untuk menjadikan program kami lebih pantas atau lebih cekap apabila berhadapan dengan kekangan yang lebih besar.

Penjelasan kod di atas

Dalam pendekatan ini kita biasanya mengulang sehingga jumlah kita kurang daripada k dan menambah jawapan kita berdasarkannya, ini adalah perubahan utama dalam kod yang berlaku apabila jumlahnya lebih besar daripada atau sama dengan k . Dalam kes ini, kita mula menambah sempadan kiri kita sehingga ia kurang daripada atau sama dengan k atau jumlahnya lebih besar daripada atau sama dengan k. Apabila pemprosesan kami berjalan lebih jauh, ia berulang melalui subarray lain yang mungkin terbentuk. Jumlah subarray baharu ini kurang daripada k ditambah pada jawapan kami, jadi jawapan kami dinaikkan.

Berbanding dengan brute force solution sebelumnya, kaedah ini sangat cekap kerana kerumitan masanya ialah O(N), di mana N ialah saiz array kami.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah mencari bilangan subarray yang jumlahnya kurang daripada k menggunakan teknik tingkap gelongsor. Kami juga mempelajari program C++ untuk masalah ini dan pendekatan lengkap kami untuk menyelesaikannya (kedua-dua remeh dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan lain-lain. Semoga artikel ini membantu anda.

Atas ialah kandungan terperinci Ditulis dalam C++, cari bilangan subarray yang jumlahnya kurang daripada K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!