Jumlah Maksimum Subarray Terbeza Dengan Panjang K

2461. Jumlah Maksimum Subarray Terbeza Dengan Panjang K

Kesukaran: Sederhana

Topik: Tatasusunan, Jadual Hash, Tetingkap Gelongsor

Anda diberi nombor tatasusunan integer dan integer k. Cari jumlah subarray maksimum semua subarray nombor yang memenuhi syarat berikut:

• Panjang subarray ialah k, dan
• Semua elemen subarray adalah berbeza.

Pulangan jumlah sub-baris maksimum semua sub-baris yang memenuhi syarat. Jika tiada subarray memenuhi syarat, kembalikan 0.

subarray ialah jujukan unsur yang tidak kosong bersebelahan dalam tatasusunan.

Contoh 1:

• Input: nombor = [1,5,4,2,9,9,9], k = 3
• Output: 15
• Penjelasan: subarray nombor dengan panjang 3 ialah:
  • [1,5,4] yang memenuhi keperluan dan mempunyai jumlah 10.
  • [5,4,2] yang memenuhi keperluan dan mempunyai jumlah 11.
  • [4,2,9] yang memenuhi keperluan dan mempunyai jumlah 15.
  • [2,9,9] yang tidak memenuhi keperluan kerana elemen 9 diulang.
  • [9,9,9] yang tidak memenuhi keperluan kerana elemen 9 diulang.
  • Kami mengembalikan 15 kerana ia adalah jumlah maksimum sub-baris semua subarray yang memenuhi syarat

Contoh 2:

• Input: nombor = [4,4,4], k = 3
• Output: 0
• Penjelasan: subarray nombor dengan panjang 3 ialah:
  • [4,4,4] yang tidak memenuhi keperluan kerana elemen 4 diulang.
  • Kami kembalikan 0 kerana tiada subarray memenuhi syarat.

Kekangan:

• 1 <= k <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁵

Petunjuk:

1. Elemen yang manakah berubah apabila bergerak daripada subarray saiz k yang berakhir pada indeks i kepada subarray saiz k yang berakhir pada indeks i 1?
2. Hanya dua elemen yang berubah, elemen di i 1 ditambah ke dalam subarray dan elemen di i - k 1 akan dialih keluar daripada subarray.
3. Lelar melalui setiap subarray saiz k dan jejaki jumlah subarray dan kekerapan setiap elemen.

Penyelesaian:

Kita boleh ikut langkah ini:

Pendekatan:

1. Tetingkap Gelongsor: Saiz tetingkap ialah k, dan kami meluncurkan tetingkap melalui tatasusunan sambil mengekalkan jumlah tetingkap semasa dan menyemak sama ada semua elemen dalam tetingkap adalah berbeza.
2. Jadual Hash (atau tatasusunan bersekutu): Gunakan tatasusunan bersekutu (jadual cincang) untuk menjejaki kekerapan elemen dalam tetingkap semasa. Jika mana-mana elemen muncul lebih daripada sekali, tetingkap itu tidak sah.
3. Mengemas kini Tetingkap: Sambil kami meluncurkan tetingkap, tambahkan elemen baharu (iaitu, elemen yang masuk ke dalam tetingkap) dan alih keluar elemen lama (iaitu, elemen yang meninggalkan tetingkap). Kemas kini jumlah dengan sewajarnya dan semak sama ada tetingkap itu sah (iaitu, semua elemen adalah berbeza).
4. Kembalikan Jumlah Maksimum: Kita perlu menjejaki jumlah maksimum yang ditemui di antara subarray yang sah.

Algoritma:

1. Mulakan kekerapan jadual cincang untuk menyimpan kekerapan elemen dalam tetingkap semasa.
2. Mulakan dengan mengira jumlah untuk tetingkap pertama bersaiz k dan simpan hasilnya jika tetingkap itu mengandungi elemen yang berbeza.
3. Gelongsor tetingkap dari kiri ke kanan dengan:
   • Mengalih keluar elemen yang meninggalkan tetingkap dari kiri.
   • Menambah elemen yang memasuki tetingkap dari sebelah kanan.
   • Kemas kini jumlah dan jadual cincang, dan semak sama ada tetingkap masih mengandungi elemen yang berbeza sahaja.
4. Jika tetingkap mempunyai elemen berbeza yang sah, kemas kini jumlah maksimum.
5. Jika tiada subarray yang sah ditemui, kembalikan 0.

Mari laksanakan penyelesaian ini dalam PHP: 2461. Jumlah Maksimum Subarray Terbeza Dengan Panjang K

  
  
  Penjelasan:




Pembolehubah:



$maxSum: Menjejaki jumlah maksimum subarray sah yang ditemui setakat ini.

$currentSum: Memegang jumlah tetingkap gelongsor semasa bersaiz k.

$freq: Jadual cincang (atau tatasusunan bersekutu) yang menyimpan kekerapan unsur dalam tetingkap semasa.



Tetingkap Gelongsor:


Kami mengulangi tatasusunan dengan gelung. Semasa kami mengalihkan tingkap, kami:


Tambahkan elemen pada indeks $i kepada jumlah dan kemas kini kekerapannya.
Jika saiz tetingkap melebihi k, kami mengalih keluar elemen pada indeks $i - k daripada jumlah dan mengurangkan kekerapannya.





Semakan Tetingkap Sah:


Setelah saiz tetingkap mencapai k (iaitu, apabila $i >= k - 1), kami menyemak sama ada semua elemen dalam tetingkap adalah berbeza dengan memastikan bahawa bilangan kekunci berbeza dalam peta frekuensi adalah sama dengan k. Jika ya, kami mengemas kini jumlah maksimum.



Kembalikan Keputusan:

Selepas melelaran melalui tatasusunan, kami mengembalikan jumlah maksimum yang ditemui. Jika tiada subarray yang sah ditemui, maxSum akan kekal 0.





  
  
  Kerumitan Masa:




O(n), dengan n ialah panjang tatasusunan nums. Setiap elemen ditambah dan dialih keluar daripada tetingkap gelongsor sekali, dan operasi jadual cincang (masukkan, keluarkan, kiraan semak) ialah O(1) secara purata.



  
  
  Kerumitan Ruang:




O(k) untuk jadual cincang yang menyimpan kekerapan elemen dalam tetingkap semasa.


Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Jumlah Maksimum Subarray Terbeza Dengan Panjang K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!