Minimum Size Subarray Sum

Q: Berapa kompleksitas waktu Minimum Size Subarray Sum?

Sliding window berjalan dalam waktu O(n) dan ruang O(1) . Perulangan di dalamnya tampak kuadratik, tetapi left hanya bergerak maju, sehingga bergerak paling banyak n kali sepanjang proses. Versi jumlah prefiks memiliki kompleksitas O(n log n) , sedangkan mencoba setiap posisi awal memiliki kompleksitas O(n²) .

Q: Mengapa sliding window membutuhkan bilangan positif?

Jendela hanya menyusut selama jumlahnya mencapai target , yaitu saat menghapus sebuah nilai hanya dapat menurunkan jumlahnya. Jika nilainya negatif, menghapusnya justru menaikkan jumlahnya. Untuk [5, -10, 20] dan target = 15 , jendela berhenti di -10, 20 dengan jumlah 10 dan tidak pernah mengukur [20] , panjang 1.

Q: Mengapa mempelajari solusi jumlah prefiks O(n log n) jika solusi O(n) tersedia?

Pewawancara sering menanyakannya setelah jawaban O(n) . Cara ini memanfaatkan nilai positif dengan cara kedua: jumlah prefiks tersusun, sehingga pencarian biner menemukan posisi saat total berjalan pertama kali melampaui ambang batas. Alat yang sama memilih indeks secara acak dengan peluang sebanding dengan bobotnya.

SedangSliding window Prefix sum

+10

Kamu mendapat bilangan bulat positif target dan sebuah array nums yang berisi bilangan bulat positif. Temukan subarray terpendek (rangkaian elemen yang bersebelahan) yang jumlahnya setidaknya target, lalu kembalikan panjangnya. Jika tidak ada subarray yang mencapai target, kembalikan 0.

Fungsi

minSubArrayLen(target: integer, nums: integer-array) → integer

targetinteger: jumlah yang harus dicapai atau dilewati oleh sebuah subarray
numsinteger-array: array bilangan bulat positif
Mengembalikaninteger: panjang subarray terpendek dengan jumlah setidaknya target, atau 0 jika tidak ada

Batasan

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

Contoh

Input: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
Output: 3
Penjelasan: Tidak ada dua angka yang bersebelahan yang jumlahnya mencapai 15: pasangan dengan jumlah terbesar adalah 9 + 3 = 12. Tiga angka bisa: 4 + 2 + 9 = 15 dan 9 + 3 + 7 = 19, jadi jawabannya adalah 3.

Pertanyaan lanjutan

Bagaimana kamu akan menyelesaikannya jika nums juga dapat berisi nol dan angka negatif, sehingga teknik sliding window tidak lagi berfungsi?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Semua nilai positif, jadi memperpanjang subarray akan menaikkan jumlahnya, sedangkan memotongnya akan menurunkannya. Karena itu, ujung terbaik untuk suatu titik awal tidak pernah bergeser ke kiri saat titik awal bergerak ke kanan, dan satu window yang bertambah dari kanan serta menyusut dari kiri akan menemukan jawabannya dalam satu kali pemindaian.

Perluas dari setiap awal

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tetapkan posisi awal, lalu tambahkan nilai ke arah kanan. Saat jumlah berjalan pertama kali mencapai target, kamu mendapatkan subarray terpendek dari posisi awal tersebut, karena setiap subarray yang lebih pendek memiliki jumlah yang lebih kecil. Catat panjangnya dan pindah ke posisi awal berikutnya; jawabannya adalah panjang terkecil dari semua posisi awal.

Jika tidak ada subarray yang mencapai target, setiap posisi awal akan berlanjut hingga akhir array: n(n+1)/2 penjumlahan, sekitar 2 × 10^8 untuk n = 2 × 10^4.

Algoritma

Tetapkan best ke 0, yang berarti belum ada yang ditemukan.
Untuk setiap indeks awal, tetapkan jumlah sementara ke 0.
Geser indeks akhir ke kanan dari posisi awal, lalu tambahkan nums[end] ke jumlah tersebut.
Saat jumlah mencapai target, simpan end-start+1 jika nilainya lebih besar daripada best, lalu berhenti memperluas rentang dari posisi awal ini.
Kembalikan best.

def minSubArrayLen(target, nums):
    n = len(nums)
    best = 0  # 0 means no subarray found yet
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total >= target:
                # The shortest subarray from this start ends here
                if best == 0 or end - start + 1 < best:
                    best = end - start + 1
                break
    return best

Jumlah awalan dan pencarian biner

Intuisi

Misalkan prefix[k] adalah jumlah dari k nilai pertama, dengan prefix[0] = 0. Jumlah nums[start..end-1] adalah prefix[end] - prefix[start], jadi untuk start yang tetap, kamu mencari end terkecil dengan prefix[end] ≥ prefix[start] + target. Nilai positif membuat prefix meningkat secara ketat, sehingga pencarian biner menemukan end tersebut.

Dalam contoh pertama, prefix adalah [0, 4, 6, 15, 18, 25, 26, 31]. Dari start 2, kamu membutuhkan 6 + 15 = 21; nilai prefix pertama yang setidaknya 21 adalah 25 pada indeks 5, jadi window-nya adalah 9, 3, 7, dengan panjang 3.

Jika prefix[n] lebih kecil dari nilai yang dibutuhkan oleh suatu start, tidak ada start setelahnya yang berhasil, jadi kamu berhenti. Itu berarti n pencarian biner: waktu O(n log n) dan ruang O(n).

Algoritma

Buat prefix dengan panjang n+1, dengan prefix[k+1] = prefix[k] + nums[k].
Untuk setiap start, hitung need = prefix[start] + target.
Jika prefix[n] < need, berhenti: tidak ada start setelahnya yang bisa berhasil.
Lakukan pencarian biner pada posisi start+1 hingga n untuk menemukan end pertama dengan prefix[end] ≥ need, lalu simpan end-start jika nilainya paling pendek sejauh ini.
Kembalikan panjang terpendek, atau 0 jika tidak ada start yang berhasil.

from bisect import bisect_left


def minSubArrayLen(target, nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values; it only grows
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    for start in range(n):
        need = prefix[start] + target
        if prefix[n] < need:
            break  # no window from here on can reach target
        # The first end with prefix[end] >= need closes the shortest window
        end = bisect_left(prefix, need, start + 1)
        if best == 0 or end - start < best:
            best = end - start
    return best

Jendela geser

Intuisi

Menghapus awal jendela secara permanen aman. Saat jendela nums[left..right] pertama kali mencapai target, jendela yang berakhir di right-1 belum mencapainya, atau perulangan akan menyusutkan jendela satu langkah lebih awal. Jadi, right adalah posisi akhir paling awal untuk awal ini, dan posisi akhir berikutnya hanya menghasilkan subarray yang lebih panjang. Catat panjangnya, hapus nums[left], lalu terus susutkan jendela selama jumlahnya masih mencapai target.

Pada contoh pertama, jumlahnya naik menjadi 4, 6, 15: catat 3 lalu hapus 4. Menambahkan 3 dan 7 menghasilkan 21: catat 4, hapus 2 (19), catat 3, hapus 9 (10). Tidak ada hasil berikutnya yang lebih pendek daripada 3.

Setiap indeks masuk ke jendela sekali dan keluar sekali, jadi perulangan bersarang melakukan total pekerjaan O(n), dengan ruang O(1).

Algoritma

Tetapkan left = 0, total = 0 dan best = 0.
Untuk setiap right, tambahkan nums[right] ke total.
Selama total ≥ target, simpan right-left+1 jika nilainya lebih baik daripada best, kurangi nums[left] dan geser left satu langkah ke kanan.
Kembalikan best, yang tetap 0 jika jumlahnya tidak pernah mencapai target.

def minSubArrayLen(target, nums):
    best = 0  # 0 means no window found yet
    total = 0  # sum of nums[left .. right]
    left = 0
    for right in range(len(nums)):
        total += nums[right]
        # Shrink while the window still reaches target
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best

Jebakan dan kasus tepi

Mengecilkan jendela dengan if, bukan while. Untuk target = 12 dan [1, 1, 2, 3, 12], menambahkan 12 membuat jumlahnya 19; if mencatat panjang 5, menghapus satu nilai, lalu melanjutkan, sehingga jendela [12] tidak pernah diukur.
Mencatat panjang setelah menghapus nums[left]. Kamu harus mengukur jendela yang jumlahnya mencapai target.
Membandingkan dengan >, bukan ≥. [3, 3, 3] dengan target = 9 memiliki jawaban 3, bukan 0.
Mengembalikan sentinel. Jika best dimulai dari n+1 atau infinity, kembalikan 0 jika tidak ada yang mencapai target, seperti pada contoh kedua.

Pertanyaan yang sering diajukan4

Berapa kompleksitas waktu Minimum Size Subarray Sum?

Sliding window berjalan dalam waktu O(n) dan ruang O(1). Perulangan di dalamnya tampak kuadratik, tetapi left hanya bergerak maju, sehingga bergerak paling banyak n kali sepanjang proses. Versi jumlah prefiks memiliki kompleksitas O(n log n), sedangkan mencoba setiap posisi awal memiliki kompleksitas O(n²).

Mengapa sliding window membutuhkan bilangan positif?

Jendela hanya menyusut selama jumlahnya mencapai target, yaitu saat menghapus sebuah nilai hanya dapat menurunkan jumlahnya. Jika nilainya negatif, menghapusnya justru menaikkan jumlahnya. Untuk [5, -10, 20] dan target = 15, jendela berhenti di -10, 20 dengan jumlah 10 dan tidak pernah mengukur [20], panjang 1.

Mengapa mempelajari solusi jumlah prefiks O(n log n) jika solusi O(n) tersedia?

Pewawancara sering menanyakannya setelah jawaban O(n). Cara ini memanfaatkan nilai positif dengan cara kedua: jumlah prefiks tersusun, sehingga pencarian biner menemukan posisi saat total berjalan pertama kali melampaui ambang batas. Alat yang sama memilih indeks secara acak dengan peluang sebanding dengan bobotnya.

Apakah jumlah subarray harus tepat sama dengan target?

Tidak. Jumlah apa pun yang lebih besar dari atau sama dengan target dihitung. Dengan target = 15, jendela 9, 3, 7 berjumlah 19 dan tetap memiliki panjang 3.

def minSubArrayLen(target, nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

target = 15
nums = [4, 2, 9, 3, 7, 1, 5]

Output yang diharapkan

Minimum Size Subarray Sum

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Perluas dari setiap awal

Jumlah awalan dan pencarian biner

Jendela geser

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan4

Soal serupa