Tulis program menggunakan C++ untuk mencari bilangan subarray dengan jumlah dalam julat tertentu

Dalam artikel ini, kami akan menggunakan program C++ untuk mencari bilangan sub-tatasusunan yang jumlahnya berada dalam julat tertentu. Kami mempunyai tatasusunan integer positif arr[] dan julat {L, R} dan kami perlu mengira jumlah bilangan subarray yang jumlahnya berada dalam julat L hingga R yang diberikan. Jadi berikut adalah contoh mudah masalah -

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}.

Cara untuk mencari penyelesaian

Kami akan menerangkan dua cara untuk menyelesaikan masalah ini menggunakan C++ -

Kaedah brute force

Kaedah brute force yang paling asas digunakan untuk mengira setiap sub Jumlah tatasusunan dan kemudian mencari sama ada jumlah itu wujud dalam julat yang diberikan. (Tetapi pendekatan ini akan membawa kita banyak masa kerana kerumitan masanya ialah O(n*n), di mana n ialah saiz tatasusunan).

Kaedah yang cekap

Save Now, kaedah yang cekap ialah menggunakan teknik sliding window, menggunakan teknik ini kita akan mengira hasilnya dengan lebih pantas atau lebih cekap dalam O(n).

Contoh

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

Output

3

Di atas perihalan kod

Dalam kaedah ini, kita mengira bilangan sub-tatasusunan yang jumlahnya kurang daripada had atas julat yang diberikan dan kemudian menolak bilangan sub-tatasusunan yang jumlahnya adalah kurang daripada had atas julat yang diberikan. Gunakan fungsi subcount untuk mendapatkan kurang daripada had bawah julat tertentu.

Fungsi subcount

Fungsi ini menggunakan teknik tetingkap gelongsor untuk mencari kiraan subarray yang kiraan kurang daripada x.

Pertama, kita mulakan dengan "Tamat" dan "Mula", yang kedua-duanya mempunyai nilai 0. Apabila kita mengulangi tatasusunan, kita mengekalkan jumlah elemen dari awal hingga akhir. Selepas itu, jika permulaan kita bersamaan dengan akhir dan jumlahnya lebih besar daripada atau sama dengan x, kita mula menggerakkan permulaan dan terus mengurangkan jumlah semasa kita mengeluarkan elemen daripada jumlah itu.

Sehingga jumlah kita menjadi kurang daripada x atau permulaan kita menjadi lebih besar daripada penghujung kita. Sekarang kita meningkatkan kiraan dengan kiraan subarray dan kemudian meningkatkan sempadan kanan sebanyak 1. Sekarang, selepas gelung luar tamat, kami mengembalikan jumlah kiraan subarray.

Kesimpulan

Dalam kertas ini, kami menyelesaikan masalah mencari bilangan subarray yang jumlahnya berada dalam julat tertentu dalam kerumitan masa O(n) menggunakan teknik tetingkap gelongsor. Kami juga belajar tentang masalah ini daripada program C++ dan cara lengkap kami boleh menyelesaikannya dengan mudah (biasa dan cekap). Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dll.

Atas ialah kandungan terperinci Tulis program menggunakan C++ untuk mencari bilangan subarray dengan jumlah dalam julat tertentu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!