. Subarray Terpendek dengan Jumlah sekurang-kurangnya K

862. Subarray Terpendek dengan Jumlah Sekurang-kurangnya K

Kesukaran: Sukar

Topik: Tatasusunan, Carian Perduaan, Baris Gilir, Tetingkap Gelongsor, Timbunan (Barisan Keutamaan), Jumlah Awalan, Baris Monotonic

Diberikan nombor tatasusunan integer dan integer k, kembalikan panjang terpendek bukan kosong subarray nombor dengan jumlah sekurang-kurangnya k. Jika tiada subarray seperti itu, kembalikan -1.

Subarray ialah bahagian bersebelahan daripada tatasusunan.

Contoh 1:

• Input: nombor = [1], k = 1
• Output: 1

Contoh 2:

• Input: nombor = [1,2], k = 4
• Output: -1

Contoh 3:

• Input: nombor = [2,-1,2], k = 3
• Output: 3

Kekangan:

1 5 -10
• 5 ⁵
1 9

Penyelesaian:

Kita perlu menggunakan pendekatan tetingkap gelongsor yang digabungkan dengan jumlah awalan dan baris gilir monoton. Berikut ialah pendekatan langkah demi langkah:

Langkah-langkah:

1. Jumlah Awalan:

   Pertama, kira tatasusunan jumlah awalan, di mana setiap elemen pada indeks i mewakili jumlah elemen dari permulaan tatasusunan hingga i. Jumlah awalan membolehkan kami mengira jumlah mana-mana subarray dalam masa tetap.

2. Baris Gilir Monotonic:

   Kami menggunakan deque (baris berhujung dua) untuk mengekalkan indeks tatasusunan prefix_sum. Deque akan dikekalkan dalam susunan jumlah awalan yang semakin meningkat.
   Ini membantu kami mencari subarray dengan cekap dengan jumlah lebih besar daripada atau sama dengan k dengan membandingkan jumlah awalan semasa dengan jumlah awalan sebelumnya.

3. Logik Tetingkap Gelongsor:

   • Untuk setiap indeks i, semak sama ada perbezaan antara jumlah awalan semasa dan sebarang jumlah awalan sebelumnya (yang disimpan dalam deque) adalah lebih besar daripada atau sama dengan k.
   • Jika ya, kira panjang subarray dan kemas kini panjang minimum jika perlu.

Algoritma:

1. Memulakan tatasusunan prefix_sum dengan saiz n 1 (dengan n ialah panjang tatasusunan input). Unsur pertama ialah 0 kerana jumlah sifar unsur ialah 0.
2. Gunakan deque untuk menyimpan indeks nilai prefix_sum. Deque akan membantu mencari subarray terpendek yang memenuhi syarat dengan cara yang cekap.
3. Untuk setiap elemen dalam tatasusunan, kemas kini prefix_sum dan semak deque untuk mencari subarray terkecil dengan jumlah lebih besar daripada atau sama dengan k.

Mari laksanakan penyelesaian ini dalam PHP: 862. Subarray Terpendek dengan Jumlah Sekurang-kurangnya K

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function shortestSubarray($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [1];
$k1 = 1;
echo shortestSubarray($nums1, $k1) . "\n"; // Output: 1

$nums2 = [1, 2];
$k2 = 4;
echo shortestSubarray($nums2, $k2) . "\n"; // Output: -1

$nums3 = [2, -1, 2];
$k3 = 3;
echo shortestSubarray($nums3, $k3) . "\n"; // Output: 3
?>

Penjelasan:

1. Susun Susun Awalan:

   • Kami mengira jumlah terkumpul tatasusunan dalam tatasusunan prefix_sum. Ini membantu dalam mengira jumlah mana-mana nombor subarray[i...j] dengan menggunakan formula prefix_sum[j 1] - prefix_sum[i].

2. Baris Gilir Monotonic:

   • Deque memegang indeks tatasusunan prefix_sum dalam susunan nilai yang semakin meningkat. Kami mengekalkan perintah ini supaya kami dapat mencari subarray terkecil dengan cekap yang jumlahnya lebih besar daripada atau sama dengan k.

3. Logik Tetingkap Gelongsor:

   • Semasa kami merentasi tatasusunan prefix_sum, kami cuba mencari subarray terkecil menggunakan perbezaan antara prefix_sum[i] semasa dan prefix_sum[deque[0]] sebelumnya].
   • Jika perbezaan lebih besar daripada atau sama dengan k, kami mengira panjang subarray dan mengemas kini panjang minimum yang ditemui.

4. Keputusan Pengembalian:

   • Jika tiada subarray yang sah ditemui, kembalikan -1. Jika tidak, kembalikan panjang subarray minimum.

Kerumitan Masa:

• Kerumitan Masa: O(n), dengan n ialah panjang tatasusunan input. Setiap elemen diproses paling banyak dua kali (sekali apabila ditambah pada deque dan sekali apabila dialih keluar).
• Kerumitan Ruang: O(n) disebabkan tatasusunan prefix_sum dan deque yang digunakan untuk menyimpan indeks.

Pendekatan ini memastikan penyelesaian berjalan dengan cekap walaupun untuk input yang besar.

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 . Subarray Terpendek dengan Jumlah sekurang-kurangnya K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!