Jadual Kandungan
Cara untuk mencari penyelesaian
Kaedah brute force
Kaedah yang cekap
Contoh
Output
Di atas perihalan kod
Fungsi subcount
Kesimpulan
Rumah pembangunan bahagian belakang C++ Tulis program menggunakan C++ untuk mencari bilangan subarray dengan jumlah dalam julat tertentu

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

Sep 01, 2023 pm 02:37 PM
c pengaturcaraan bawahan julat dan

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}.
Salin selepas log masuk

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;
}
Salin selepas log masuk

Output

3
Salin selepas log masuk

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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Artikel Panas

R.E.P.O. Kristal tenaga dijelaskan dan apa yang mereka lakukan (kristal kuning)
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Tetapan grafik terbaik
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Cara Memperbaiki Audio Jika anda tidak dapat mendengar sesiapa
3 minggu yang lalu By 尊渡假赌尊渡假赌尊渡假赌

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Gunakan C++ untuk menulis kod untuk mencari nombor bukan persegi Nth Gunakan C++ untuk menulis kod untuk mencari nombor bukan persegi Nth Aug 30, 2023 pm 10:41 PM

Kita semua tahu nombor yang bukan kuasa dua mana-mana nombor, seperti 2, 3, 5, 7, 8, dll. Terdapat N nombor bukan persegi, dan adalah mustahil untuk mengetahui setiap nombor. Jadi, dalam artikel ini, kami akan menerangkan segala-galanya tentang nombor tanpa kuasa dua atau bukan kuasa dua dan cara untuk mencari nombor bukan kuasa dua N dalam C++. Nombor bukan kuasa dua ken Jika nombor ialah kuasa dua integer, maka nombor itu dipanggil kuasa dua sempurna. Beberapa contoh nombor kuasa dua sempurna ialah -1isquareof14issquareof29issquareof316issquareof425issquareof5 Jika nombor bukan kuasa dua mana-mana integer, maka nombor itu dipanggil bukan kuasa dua. Sebagai contoh, 15 nombor bukan kuasa dua yang pertama ialah -2,3,5,6,

Algoritma penyongsangan untuk putaran kanan tatasusunan yang ditulis dalam C++ Algoritma penyongsangan untuk putaran kanan tatasusunan yang ditulis dalam C++ Sep 08, 2023 pm 08:17 PM

Dalam artikel ini, kita akan mempelajari tentang algoritma pembalikan untuk memutar tatasusunan yang diberikan ke kanan dengan elemen k, contohnya −Input:arr[]={4,6,2,6,43,7,3,7}, k= 4Output:{43,7,3,7,4,6,2,6}Penjelasan:Pusingeachelementofarrayby4-elementtotherightmemberi{43,7,3,7,4,6,2,6}.Input:arr[]= {8 ,5,8,2,1,4,9,3},k=3Output:{4,9,3,8,5,8,2,1} Cari penyelesaian

Dalam pengaturcaraan C, cari luas bulatan Dalam pengaturcaraan C, cari luas bulatan Aug 25, 2023 pm 10:57 PM

Bulatan ialah rajah tertutup. Semua titik pada bulatan adalah sama jarak dari titik di dalam bulatan. Titik tengah dipanggil pusat bulatan. Jarak dari satu titik ke pusat bulatan dipanggil jejari. Luas ialah perwakilan kuantitatif bagi rentang dimensi bagi rajah tertutup. Luas bulatan ialah kawasan yang tertutup dalam dimensi bulatan. Formula untuk mengira luas bulatan, Luas=π*r*r Untuk mengira luas, kami memberikan jejari bulatan sebagai input, kami akan menggunakan formula untuk mengira luas, algoritma LANGKAH1: Takeradiusasinputfromtheuserusingstdinput.STEP2 : Kirakaluas bulatan, luas=(

Di Jawa, cari jumlah subarray maksimum subarray selepas membahagikan tatasusunan kepada subarray berdasarkan pertanyaan yang diberikan Di Jawa, cari jumlah subarray maksimum subarray selepas membahagikan tatasusunan kepada subarray berdasarkan pertanyaan yang diberikan Aug 29, 2023 am 11:21 AM

Kami mempunyai dua tatasusunan integer, satu dengan elemen yang dikira dan satu lagi dengan titik pisah yang diperlukan untuk memisahkan tatasusunan untuk menghasilkan subset, kita perlu mengira jumlah setiap subset dalam setiap pecahan dan mengembalikan subset maksimum Mari kita lihat contoh Pemahaman: - input −intarr[]=intarr[]={9,4,5,6,7}intsplitPoints[]={0,2,3,1}; 13,9,9] Penjelasan − Di sini kita menguraikan tatasusunan mengikut titik pecahannya dan mendapatkan subset maksimum selepas setiap pecahan dan selepas pecahan pertama → {9} dan {4,5,6,7 }>>Jumlah maksimum subarray ialah -22 selepas pemisahan kedua→{9},{4

Cari bilangan pasangan unik dalam tatasusunan menggunakan C++ Cari bilangan pasangan unik dalam tatasusunan menggunakan C++ Sep 07, 2023 am 11:53 AM

Kami memerlukan pengetahuan yang betul untuk mencipta beberapa pasangan unik dalam sintaks tatasusunan C++. Semasa mencari bilangan pasangan unik, kami mengira semua pasangan unik dalam tatasusunan yang diberikan iaitu semua pasangan yang mungkin boleh dibentuk di mana setiap pasangan harus unik. Contohnya -Input:array[]={5,5,9}Output:4Explanation:Thenumberofalluniquepairsare(5,5),(5,9),(9,5)and(9,9).Input:array[] = {5,4,3,2,2}Output:16 Cara Mencari Penyelesaian Terdapat dua cara untuk menyelesaikan masalah ini, iaitu −

Tulis kod menggunakan C++ untuk mencari bilangan subarray dengan nilai minimum dan maksimum yang sama Tulis kod menggunakan C++ untuk mencari bilangan subarray dengan nilai minimum dan maksimum yang sama Aug 25, 2023 pm 11:33 PM

Dalam artikel ini, kami akan menggunakan C++ untuk menyelesaikan masalah mencari bilangan subarray yang nilai maksimum dan minimumnya adalah sama. Berikut ialah contoh masalah −Input:array={2,3,6,6,2,4,4,4}Output:12Penjelasan:{2},{3},{6},{6}, {2 },{4},{4},{4},{6,6},{4,4},{4,4}dan{4,4,4}arethesubarraysyang boleh dibentuk denganmaksimumdanminimumelemensama.Input:array={3, 3, 1,5,

Ditulis dalam C++, cari bilangan hubungan refleksif pada set Ditulis dalam C++, cari bilangan hubungan refleksif pada set Aug 26, 2023 pm 08:17 PM

Dalam artikel ini kami akan menerangkan cara untuk mencari hubungan refleksif pada set. Dalam masalah ini, kita diberi nombor n, dan set n nombor asli, dan kita mesti menentukan bilangan hubungan refleksif. Hubungan refleksif - Suatu hubungan R dikatakan sebagai hubungan refleksif pada set A jika bagi setiap 'a' dalam set A, (a, a) tergolong dalam hubungan R. Contohnya -Input:x=1Output:1Explanation:set={1},reflexiverelationsonA*A:{{1}}Input:x=2Output:4Explanation:set={1,2},reflexiverelationsonA*

Balikkan kumpulan senarai pautan berganda mengikut saiz yang diberikan menggunakan C++ Balikkan kumpulan senarai pautan berganda mengikut saiz yang diberikan menggunakan C++ Sep 04, 2023 am 09:49 AM

Dalam masalah ini, kita diberikan penunjuk kepada kepala senarai terpaut dan integer k. Dalam kumpulan saiz k, kita perlu membalikkan senarai terpaut. Contohnya -Input:1<->2<->3<->4<->5(doublylinkedlist),k=3Output:3<->2<->1<->5<->4 mencari penyelesaian Kaedah Dalam masalah ini, kami akan merumuskan algoritma rekursif untuk menyelesaikan masalah ini. Dalam kaedah ini kita akan menggunakan rekursi dan menyelesaikan masalah menggunakan rekursi. Contoh#include<iostream&

See all articles