Longest Subarray with Sum K

+10

Diberikan bilangan bulat nums dan target k, kembalikan panjang subarray terpanjang yang jumlah elemennya tepat k. Subarray adalah rentang elemen yang berurutan, dengan panjang minimal satu elemen. Beberapa nilai mungkin nol atau kurang dari nol. Jika tidak ada subarray yang jumlahnya sama dengan k, kembalikan 0.

Fungsi

longestSubarrayWithSumK(nums: integer-array, k: integer) → integer

numsinteger-array: bilangan bulat yang akan dicari, termasuk bilangan negatif dan nol
kinteger: jumlah tepat yang harus dimiliki subarray
Mengembalikaninteger: panjang subarray terpanjang yang jumlahnya sama dengan k, atau 0 jika tidak ada

Batasan

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Setiap jumlah awalan tetap berada di antara -2 × 10⁸ dan 2 × 10⁸, jadi bilangan bulat 32-bit sudah cukup.
Kembalikan 0 jika tidak ada subarray yang jumlahnya sama dengan k.

Contoh

Input: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Output: 5
Penjelasan: Tiga perulangan menghasilkan jumlah 5: [2, 3] di akhir, [2, -1, 3, 1] di awal, dan [3, 1, -4, 2, 3] pada indeks 2 sampai 6. Yang terakhir adalah yang terpanjang, dengan 5 elemen.

Input: nums = [4, 1, 1, 2, -1, 1]k = 3
Output: 4
Penjelasan: [1, 1, 2, -1] pada indeks 1 hingga 4 dan [1, 2, -1, 1] pada indeks 2 hingga 5 sama-sama berjumlah 3 dengan 4 elemen. Kamu mengembalikan panjang, jadi hasil seri tidak masalah.

Pertanyaan lanjutan

Bagaimana cara menemukan subarray terpanjang yang jumlahnya paling banyak k, dengan nilai negatif tetap diperbolehkan?

Petunjuk

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

0 dari 3 dibuka

Solusi

Jumlah kumulatif membuat jumlah subarray mana pun menjadi satu pengurangan: elemen setelah indeks s hingga indeks i berjumlah prefix[i] - prefix[s]. Ingat indeks pertama tempat setiap jumlah muncul, lalu satu kali penelusuran menemukan kecocokan terpanjang yang berakhir di setiap posisi.

Tumbuhkan setiap subarray dari tiap titik awal

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Dari setiap titik awal, lanjutkan ke kanan dan tambahkan setiap elemen ke total berjalan. Setiap kali total sama dengan k, catat panjangnya. Setiap subarray adalah satu pasangan titik awal dan titik akhir, jadi tidak ada yang terlewat. Terus lanjutkan meskipun total sudah melewati k: dari indeks 2 pada contoh pertama, totalnya adalah 3, 4, 0, 2, 5, dan nilai -4 membuat total terakhir mencapai 5.

Ada sekitar n²/2 pasangan: 2 × 10^8 penjumlahan untuk n = 2 × 10^4.

Algoritma

Tetapkan best ke 0.
Untuk setiap start, tetapkan total ke 0.
Pindahkan end dari start ke indeks terakhir dan tambahkan nums[end] ke total.
Saat total sama dengan k, tetapkan best ke nilai yang lebih besar antara best dan end - start + 1.
Kembalikan best.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

Jumlah awalan dengan indeks pertama setiap jumlah

Intuisi

Sebuah perulangan yang berakhir pada indeks i jumlahnya sama dengan k tepat ketika ada jumlah sebelumnya yang sama dengan prefix - k. Jika beberapa jumlah sebelumnya memenuhi, jumlah yang pertama memulai perulangan terpanjang, jadi map hanya menyimpan setiap jumlah pada kemunculan pertamanya. Kemunculan berikutnya hanya bisa memulai perulangan yang lebih pendek. Isi map terlebih dahulu dengan jumlah 0 pada indeks -1, sehingga kecocokan yang dimulai pada indeks 0 memiliki panjang i + 1.

Pada contoh pertama, jumlahnya adalah 2, 1, 4, 5, 1, 3, 6. Pada indeks 6, 6 - 5 = 1 pertama kali muncul pada indeks 1, sehingga menghasilkan panjang 5. Jumlah 1 muncul kembali pada indeks 4, dan mempertahankan indeks 1 akan menemukan perulangan tersebut.

Satu pencarian untuk setiap elemen menghasilkan waktu O(n), dan map menyimpan paling banyak n + 1 jumlah.

Algoritma

Buat map first yang menyimpan total 0 pada indeks -1, lalu tetapkan prefix dan best ke 0.
Untuk setiap indeks i, tambahkan nums[i] ke prefix.
Jika prefix - k ada di map pada indeks start, tetapkan best ke nilai yang lebih besar antara best dan i - start.
Jika prefix belum ada di map, simpan nilainya dengan indeks i.
Kembalikan best.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

Jebakan dan kasus tepi

Menimpa indeks yang tersimpan setiap kali total berulang akan mempertahankan awal terbaru dan menemukan kecocokan yang lebih pendek. Contoh pertama mengembalikan 4, bukan 5, karena total 1 berpindah dari indeks 1 ke indeks 4.
Jendela yang menyusut saat jumlahnya lebih besar dari k juga mengembalikan 4 pada contoh pertama. Jendela itu berakhir dengan isi [-1, 3, 1, -4, 2, 3] yang jumlahnya 4 dan tidak pernah menghapus -1.
Tidak menyertakan total 0 pada indeks -1 membuat semua kecocokan yang dimulai pada indeks 0 terlewat: [5, 0, 0, 0] dengan k = 5 mengembalikan 0, bukan 4.
Indeks yang tersimpan adalah posisi sebelum subarray, jadi panjangnya adalah i - start. Menambahkan 1 akan menghitung satu elemen terlalu banyak.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu untuk Subarray Terpanjang dengan Jumlah K?

Waktu O(n) dan ruang tambahan O(n) dengan total berjalan dan map indeks pertama: satu pencarian dan paling banyak satu penyisipan per elemen. Menumbuhkan setiap subarray dari setiap titik awal membutuhkan waktu O(n²) dan ruang O(1).

Mengapa sliding window gagal saat array berisi angka negatif?

Sliding window mengasumsikan bahwa menambahkan elemen akan menaikkan jumlah, sedangkan menghapus elemen akan menurunkannya. Jika ada nilai negatif, window yang jumlahnya terlalu besar masih bisa mencapai k setelah elemen negatif masuk, dan window yang jumlahnya terlalu kecil mungkin perlu menghapus elemen negatif di sebelah kirinya. Window tidak dapat menentukan langkah mana yang tepat.

Bisakah Longest Subarray with Sum K diselesaikan dengan ruang tambahan O(1)?

Hanya jika tidak ada nilai yang negatif. Dengan begitu, jumlah tidak pernah berkurang saat jendela membesar, dan dua pointer menemukan jendela terpanjang dengan jumlah k dalam waktu O(n) dan ruang O(1). Jika ada nilai negatif, kamu memerlukan map total, atau pemindaian O(n²).

def longestSubarrayWithSumK(nums, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

Output yang diharapkan