Subarray Sum Equals K

+10

Kamu mendapatkan sebuah array bilangan bulat nums dan sebuah bilangan bulat k. Hitung jumlah subarray yang elemen-elemennya berjumlah tepat k. Subarray adalah rangkaian satu elemen atau lebih yang bersebelahan. Dua subarray dihitung secara terpisah jika dimulai atau berakhir pada posisi yang berbeda, meskipun nilainya sama. Nilainya bisa negatif atau nol.

Fungsi

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

numsinteger-array: array bilangan bulat yang dapat menyimpan nilai negatif dan nol
kinteger: jumlah yang harus dicapai oleh sebuah subarray agar dihitung
Mengembalikaninteger: jumlah subarray yang elemen-elemennya berjumlah k

Batasan

1 ≤ nums.length ≤ 2 × 10⁴
-1000 ≤ nums[i] ≤ 1000
-10⁷ ≤ k ≤ 10⁷
An array sepanjang ini memiliki paling banyak 200,010,000 subarray, jadi jawabannya muat dalam integer signed 32-bit.

Contoh

Input: nums = [3, 4, -7, 1, 3, 3, 1, -4]k = 7
Output: 4
Penjelasan: Empat perulangan berjumlah 7: [3, 4], [1, 3, 3], [3, 3, 1] dan [3, 4, -7, 1, 3, 3]. Pada yang terakhir, -7 membatalkan 3 dan 4.

Input: nums = [1, -1, 0]k = 0
Output: 3
Penjelasan: Tiga subarray memiliki jumlah 0: [1, -1], [0], dan seluruh array [1, -1, 0]. Urutan [-1, 0] memiliki jumlah -1, jadi tidak dihitung.

Input: nums = [2, 2, 2]k = 4
Output: 2
Penjelasan: Perulangan [2, 2] pada indeks 0 dan 1 serta perulangan [2, 2] pada indeks 1 dan 2 memiliki nilai yang sama, tetapi berada di posisi yang berbeda, jadi keduanya dihitung.

Pertanyaan lanjutan

Bagaimana kamu mengubah solusi agar mengembalikan panjang subarray terpanjang yang jumlahnya sama dengan k, dengan waktu tetap O(n)?

Petunjuk

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

0 dari 3 dibuka

Solusi

Memeriksa hingga 2 × 10^8 subarray terlalu lambat, dan nilai negatif membuat teknik jendela geser tidak bisa digunakan. Jumlah subarray adalah selisih antara dua jumlah prefix, jadi subarray yang berakhir di sini berjumlah k untuk setiap jumlah prefix sebelumnya yang nilainya sama dengan jumlah saat ini dikurangi k. Hash map menghitung semuanya dalam satu kali lintasan.

Setiap dimulai dengan total berjalan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tetapkan indeks pertama start, lalu geser end ke kanan dan tambahkan nums[end] ke total yang terus diperbarui. total selalu menyimpan jumlah dari start hingga end, jadi mengunjungi setiap pasangan akan memeriksa setiap subarray satu kali, dengan satu penjumlahan untuk masing-masing.

Jangan berhenti saat total melewati k. Nilai negatif berikutnya dapat membuatnya kembali: pada contoh pertama, total dari indeks 0 berubah menjadi 3, 7, 0, 1, 4, 7, dengan kecocokan kedua pada indeks 5.

Biayanya adalah jumlah pasangan, sekitar 2 × 10^8 saat n = 2 × 10^4.

Algoritma

Atur count menjadi 0.
Untuk setiap start dari 0 hingga n-1, atur total menjadi 0.
Untuk setiap end dari start hingga n-1, tambahkan nums[end] ke total.
Jika total sama dengan k, tambahkan 1 ke count, lalu lanjutkan apa pun hasilnya.
Kembalikan count.

def subarraySum(nums, k):
    n = len(nums)
    count = 0
    for start in range(n):
        total = 0
        # Grow the subarray that begins at start, one element at a time
        for end in range(start, n):
            total += nums[end]
            if total == k:
                count += 1
    return count

Jumlah awalan dengan peta hitungan

Intuisi

Misalkan prefix[j] adalah jumlah j elemen pertama, dengan prefix[0] = 0 untuk prefix kosong. Subarray dari indeks i hingga indeks j-1 memiliki jumlah prefix[j] - prefix[i]. Jadi, setiap jumlah prefix sebelumnya yang sama dengan prefix saat ini dikurangi k menandai awal dari satu subarray cocok yang berakhir di sini. Simpan jumlah kemunculannya, bukan sebagai set: jumlah prefix yang berulang memulai subarray berbeda setiap kali.

Pada contoh pertama, jumlah prefix-nya adalah 0, 3, 7, 0, 1, 4, 7, 8, 4. Angka 7 pertama menemukan satu angka 0, menghasilkan [3, 4]. Angka 7 kedua menemukan dua angka 0, menghasilkan [3, 4, -7, 1, 3, 3] dan [1, 3, 3]. Angka 8 menemukan satu angka 1, menghasilkan [3, 3, 1].

Cari sebelum mencatat prefix saat ini, atau dengan k = 0, prefix tersebut akan cocok dengan dirinya sendiri sebagai subarray kosong. Setiap elemen memerlukan satu pencarian dan satu pembaruan: waktu dan ruang O(n).

Algoritma

Buat map seen dengan seen[0] = 1, lalu tetapkan prefix dan count ke 0.
Untuk setiap elemen, tambahkan nilainya ke prefix.
Tambahkan seen[prefix - k] ke count, dengan membaca kunci yang tidak ada sebagai 0.
Tambahkan 1 ke seen[prefix].
Kembalikan count.

def subarraySum(nums, k):
    # seen[p] = how many prefixes so far add up to p; the empty prefix adds up to 0
    seen = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        # Each earlier prefix equal to prefix - k starts a subarray that ends here and sums to k
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Jebakan dan kasus tepi

Jendela geser yang menyusut setelah jumlah melewati k tidak berfungsi jika ada nilai negatif: pada contoh pertama, hasilnya 2, bukan 4. Keluar dari perulangan bagian dalam brute force pada titik itu juga gagal dengan cara yang sama.
Tidak menyertakan seen[0] = 1. Untuk nums = [5] dan k = 5, hasilnya 0, bukan 1.
Mencatat prefiks saat ini sebelum pencarian. Dengan k = 0, [1, -1, 0] menghasilkan 6, bukan 3.
Menggunakan set jumlah prefiks sebagai pengganti peta hitungan. Untuk [0, 0, 0] dan k = 0, pengulangan tidak terhitung; jawabannya adalah 6.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk Subarray Sum Equals K?

Solusi prefix sum dan hash map berjalan dalam waktu O(n) dan menggunakan ruang ekstra O(n): satu kali penelusuran, dengan satu pencarian dan satu pembaruan untuk setiap elemen. Memeriksa setiap subarray dengan total berjalan membutuhkan waktu O(n²).

Mengapa sliding window tidak berfungsi untuk Subarray Sum Equals K?

Sliding window membutuhkan jumlah yang meningkat saat window membesar dan menurun saat window mengecil. Nilai negatif mengacaukan hal itu: window yang terlalu besar masih bisa menjadi cocok nantinya, jadi tidak ada aturan yang menentukan kapan harus menggeser tepi kiri. Jika hanya ada nilai positif, window menyelesaikannya dalam waktu O(n) dan ruang O(1).

Mengapa hash map dimulai dengan 0 dipetakan ke 1?

Entri itu mewakili prefiks kosong sebelum elemen pertama, yang jumlahnya 0. Jumlah subarray yang dimulai pada indeks 0 sama dengan jumlah prefiks saat ini dikurangi 0, jadi tanpa entri itu, subarray tersebut tidak pernah dihitung. Untuk nums = [5] dan k = 5, pencarian 5 - 5 = 0 menemukannya.

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

Tes #1

Tes #2

Tes #3

Argumen

nums = [3, 4, -7, 1, 3, 3, 1, -4]
k = 7

Output yang diharapkan