4Sum

Q: Apa kompleksitas waktu 4Sum?

O(n³). Kedua perulangan memilih sekitar n²/2 pasangan (i, j) , dan setiap pasangan menjalani satu pemindaian dua pointer paling banyak n langkah; pengurutan O(n log n) kecil dibandingkan itu.

Q: Bagaimana cara menggeneralisasi 4Sum menjadi kSum?

Tulis kSum(nums, target, k) pada list yang sudah diurutkan. Untuk k = 2, fungsi ini menjalankan sapuan dua pointer. Untuk k yang lebih besar, fungsi ini melakukan perulangan pada nilai pertama, melewati nilai yang berulang, lalu memanggil dirinya sendiri dengan k-1 dan target - nums[i] pada nilai-nilai di sebelah kanan. Setiap tingkat menambahkan faktor n, sehingga kSum membutuhkan biaya O(n^(k-1)).

Q: Apakah 4Sum dapat diselesaikan dalam O(n²)?

Kamu dapat mengelompokkan jumlah n²/2 pasangan dalam hash map dan mencocokkan setiap pasangan dengan pasangan yang jumlahnya sama dengan target dikurangi jumlah pasangan itu sendiri. Cara ini cepat jika hanya sedikit pasangan yang memiliki jumlah sama, tetapi satu jumlah bisa memiliki O(n²) pasangan, sehingga kasus terburuknya tidak lebih baik daripada O(n³).

SedangTwo pointers Pengurutan

+10

Kamu mendapatkan sebuah list bilangan bulat nums dan sebuah bilangan bulat target. Kembalikan setiap quadruplet [a, b, c, d] yang keempat nilainya berada pada empat posisi berbeda di nums dan jumlahnya sama dengan target. Tulis setiap quadruplet dengan nilai-nilainya dalam urutan tidak menurun. Jika empat nilai yang sama dapat dipilih dari posisi berbeda, quadruplet tersebut tetap muncul satu kali. Urutkan jawaban berdasarkan nilai pertama, lalu kedua, lalu ketiga. Jika tidak ada quadruplet yang memenuhi, kembalikan list kosong.

Fungsi

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: angka yang bisa dipilih, setidaknya satu
targetinteger: jumlah yang harus dicapai setiap kuadruplet
Mengembalikaninteger-2d-array: kuadruplet berbeda dengan jumlah target, masing-masing diurutkan, daftarnya juga diurutkan; daftar kosong jika tidak ada

Batasan

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
Jumlah empat nilai apa pun berada di antara -4 × 10⁸ dan 4 × 10⁸, sehingga muat dalam bilangan bulat 32-bit.
Setiap quadruplet yang berisi empat nilai sama dihitung sebagai satu.

Contoh

Input: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Output: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Penjelasan: Masing-masing dari empat kuadruplet berjumlah 1, misalnya -3 + (-1) + 2 + 3. Dua yang diawali dengan -3 muncul lebih dahulu, diurutkan berdasarkan nilai keduanya: -1 sebelum 0.

Input: nums = [4, 4, 4, 4, 4, 4]target = 16
Output: [[4, 4, 4, 4]]
Penjelasan: Semua 15 pilihan empat posisi dari enam menghasilkan empat angka 4 yang jika dijumlahkan menjadi 16, jadi [4, 4, 4, 4] muncul satu kali.

Input: nums = [1, 5, 2, 9]target = 3
Output: []
Penjelasan: Satu-satunya pilihan adalah keempat angka, dan 1 + 5 + 2 + 9 = 17, bukan 3, jadi jawabannya adalah list kosong.

Pertanyaan lanjutan

Hitung banyaknya himpunan empat posisi yang nilainya berjumlah target, bukan kuadruplet yang berbeda. Contoh kedua memiliki 15. Bisakah kamu melakukannya dalam O(n²)?

Petunjuk

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

0 dari 3 dibuka

Solusi

Memeriksa setiap kombinasi empat posisi membutuhkan biaya O(n⁴), dan nilai yang berulang membuat quadruplet yang sama berkali-kali. Terapkan reduksi 3Sum satu tingkat lebih dalam: urutkan, tetapkan dua nilai pertama dengan dua loop, cari pasangan terakhir dengan dua pointer, dan lewati nilai yang berulang di setiap tingkat.

Coba setiap set yang terdiri dari empat

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Urutkan terlebih dahulu agar posisi i < j < k < l menyimpan nilai dalam urutan tidak menurun dan setiap quadruplet ditulis dengan urutan yang benar. Empat perulangan bersarang menjangkau setiap pilihan empat posisi. Untuk menghindari pengulangan, suatu perulangan beralih ke langkah berikutnya jika posisi berikutnya menyimpan nilai yang sudah dicobanya pada langkah sebelumnya. Untuk enam angka 4, setiap perulangan hanya mencoba posisi pertamanya, sehingga [4, 4, 4, 4] muncul sekali, bukan 15 kali.

Untuk 200 angka, ada 64,684,950 himpunan berisi empat angka, dan jumlahnya bertambah sekitar 16 kali saat n menjadi dua kali lipat.

Algoritma

Urutkan nums.
Buat empat perulangan bersarang untuk i < j < k < l, masing-masing dimulai satu posisi setelah perulangan yang mengelilinginya.
Di setiap perulangan, lewati posisi yang bukan posisi pertama perulangan tersebut dan memiliki nilai yang sama dengan posisi sebelumnya.
Catat [nums[i], nums[j], nums[k], nums[l]] jika keempatnya berjumlah target. Perulangan menghasilkan nilai-nilai tersebut dalam urutan terurut.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Pengurutan, dua perulangan, dua pointer

Intuisi

Tetapkan nums[i] dan nums[j], lalu yang tersisa adalah masalah mencari pasangan: temukan dua nilai di sebelah kanan j yang jumlahnya sama dengan target - nums[i] - nums[j]. Pada list yang sudah diurutkan, satu kali penelusuran sudah cukup. Mulai lo dari j+1 dan hi dari indeks terakhir. Jika jumlahnya kurang dari target, geser lo ke kanan; jika jumlahnya lebih dari target, geser hi ke kiri.

Setiap pergeseran membuang nilai yang tidak mungkin menjadi bagian dari jawaban. Jika jumlahnya terlalu kecil, bahkan nilai terbesar yang tersisa, nums[hi], tidak cukup untuk dipasangkan dengan nums[lo], jadi nums[lo] dapat dibuang. Jika jumlahnya terlalu besar, nums[hi] dibuang dengan alasan yang serupa. Satu pasangan (i, j) memerlukan paling banyak n pergeseran, jadi n²/2 pasangan membutuhkan O(n³).

Pada contoh pertama, saat i berada di -3 dan j berada di -1, lo bergeser dari 0 melewati 1 hingga mencapai 2, saat -3 + (-1) + 2 + 3 = 1.

Algoritma

Urutkan nums.
Untuk setiap i, lewati jika i > 0 dan nums[i] sama dengan nums[i-1].
Untuk setiap j setelah i, lewati jika j > i+1 dan nums[j] sama dengan nums[j-1].
Tetapkan lo = j+1 dan hi = n-1. Selama lo < hi, bandingkan jumlah keempat nilai dengan target: jika kurang dari nilai tersebut, geser lo ke kanan; jika lebih, geser hi ke kiri.
Jika cocok, catat kuadruplet, geser kedua pointer, lalu majukan lo selama nilainya sama dengan nilai yang digunakan sebelumnya.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

Jebakan dan kasus tepi

Melewati j setiap kali nums[j] sama dengan nums[j-1]. Pada j = i+1, perbandingan dilakukan dengan nilai yang digunakan i, sehingga [2, 2, 2, 2, 2] dengan target 8 kehilangan [2, 2, 2, 2].
Menyalin early exit 3Sum, nums[i] > target. Dengan [-5, -4, -3, -2, -1] dan target -10, perulangan berhenti di -5 dan melewatkan [-4, -3, -2, -1].
list yang lebih pendek dari empat angka. Dengan satu atau dua angka, n-3 bernilai negatif: 0..<(n - 3) menyebabkan trap di Swift, dan n - 3 pada usize Rust mengalami underflow. Kembalikan list kosong terlebih dahulu.
Mengumpulkan quadruplet dalam hash set lalu mengembalikannya tanpa diurutkan.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu 4Sum?

O(n³). Kedua perulangan memilih sekitar n²/2 pasangan (i, j), dan setiap pasangan menjalani satu pemindaian dua pointer paling banyak n langkah; pengurutan O(n log n) kecil dibandingkan itu.

Bagaimana cara menggeneralisasi 4Sum menjadi kSum?

Tulis kSum(nums, target, k) pada list yang sudah diurutkan. Untuk k = 2, fungsi ini menjalankan sapuan dua pointer. Untuk k yang lebih besar, fungsi ini melakukan perulangan pada nilai pertama, melewati nilai yang berulang, lalu memanggil dirinya sendiri dengan k-1 dan target - nums[i] pada nilai-nilai di sebelah kanan. Setiap tingkat menambahkan faktor n, sehingga kSum membutuhkan biaya O(n^(k-1)).

Apakah 4Sum dapat diselesaikan dalam O(n²)?

Kamu dapat mengelompokkan jumlah n²/2 pasangan dalam hash map dan mencocokkan setiap pasangan dengan pasangan yang jumlahnya sama dengan target dikurangi jumlah pasangan itu sendiri. Cara ini cepat jika hanya sedikit pasangan yang memiliki jumlah sama, tetapi satu jumlah bisa memiliki O(n²) pasangan, sehingga kasus terburuknya tidak lebih baik daripada O(n³).

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

Tes #1

Tes #2

Tes #3

Argumen

nums = [3, -1, 0, 2, -2, 1, -3]
target = 1

Output yang diharapkan

[[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]