3Sum

+10

Kamu mendapatkan sebuah list bilangan bulat nums. Temukan setiap triplet [a, b, c] nilai yang diambil dari tiga posisi berbeda dalam nums dengan a + b + c = 0. Tulis setiap triplet dalam urutan tidak menurun (a ≤ b ≤ c) dan cantumkan setiap triplet yang berbeda satu kali, meskipun beberapa pilihan posisi menghasilkan triplet yang sama. Kembalikan triplet yang diurutkan berdasarkan nilai pertamanya, lalu nilai keduanya.

Fungsi

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: daftar bilangan bulat, dengan setidaknya tiga elemen
Mengembalikaninteger-2d-array: setiap triplet berbeda yang jumlahnya 0, masing-masing dalam urutan tidak menurun, daftar diurutkan

Batasan

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
Setidaknya satu tripel berjumlah 0.
Dua triplet dianggap sama jika keduanya menyimpan tiga nilai yang sama.

Contoh

Input: nums = [-2, 0, 1, 1, -1, 2]
Output: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Penjelasan: Tiga triplet menghasilkan 0. [-2, 1, 1] menggunakan nilai 1 dua kali karena 1 berada di dua posisi; [-1, 0, 1] dapat menggunakan salah satu nilai 1, tetapi hanya muncul sekali.

Input: nums = [0, 0, 0, 0]
Output: [[0, 0, 0]]
Penjelasan: Tiga nol mana pun dari empat nol jika dijumlahkan hasilnya 0. Ada empat pilihan posisi, tetapi semuanya menghasilkan triplet yang sama, jadi jawabannya memuat [0, 0, 0] satu kali.

Pertanyaan lanjutan

Pola yang sama menyelesaikan 4Sum: tetapkan dua nilai dan jalankan dua pointer pada bagian sisanya. Bisakah kamu menulisnya dalam O(n³) dan memastikan aturan duplikat tetap benar di setiap tingkat?

Petunjuk

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

0 dari 3 dibuka

Solusi

Memeriksa setiap triplet membutuhkan biaya O(n³), dan setiap triplet harus muncul satu kali meskipun nilainya berulang. Pengurutan mengatasi keduanya: nilai yang sama berada berdampingan, sehingga kamu melewati pengulangan dengan membandingkan nilai yang bersebelahan. Setelah nilai terkecil ditetapkan, dua nilai lainnya membentuk masalah penjumlahan pasangan pada list yang telah diurutkan.

Coba setiap tripel

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Urutkan list, lalu coba setiap tiga posisi i < j < k. Nilainya tersusun berurutan, jadi triplet langsung tertulis dengan benar saat kamu menemukannya, dan perulangan bersarang tidak melewatkan apa pun. Setiap perulangan melewati posisi yang nilainya sama dengan nilai yang dicoba perulangan itu sebelumnya, sehingga setiap triplet berbeda muncul satu kali. [-2, 1, 1] tetap menggunakan kedua angka satu, karena perbandingan untuk melewati nilai hanya dilakukan di dalam satu perulangan.

Ada sekitar n³/6 tripel: n = 3000 berarti 4.5 × 10^9 jumlah.

Algoritma

Urutkan nums.
Lakukan perulangan pada i, lalu j mulai dari i+1, lalu k mulai dari j+1. Pada setiap perulangan, lewati posisi yang nilainya sama dengan nilai yang dicoba oleh perulangan itu sebelumnya.
Catat [nums[i], nums[j], nums[k]] jika ketiganya berjumlah 0, lalu kembalikan triplet sesuai urutan penemuannya.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            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):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

Perbaiki satu nilai, temukan pasangannya dengan hash set

Intuisi

Dengan nums[i] tetap, kamu memerlukan dua nilai setelahnya yang jumlahnya sama dengan -nums[i]: Two Sum. Telusuri j ke kanan dari i dengan set berisi nilai-nilai yang sudah dilewati. Jika need = -nums[i] - nums[j] ada di dalam set, [nums[i], need, nums[j]] jumlahnya 0. Satu i memerlukan O(n) secara rata-rata, sehingga pencariannya memerlukan O(n²).

Setelah menemukan kecocokan, lewati salinan nums[j] dengan memajukan j: karena nilai pertama dan ketiga tetap, nilai tengah juga tetap. need berasal dari posisi terurut yang lebih awal, jadi triplet tersusun berurutan, tetapi saat j bergerak ke kanan, need mengecil: satu i menghasilkan [-2, 1, 1] sebelum [-2, 0, 2]. Balik urutan setiap kelompok sebelum menambahkannya.

Algoritma

Urutkan nums.
Untuk setiap i, berhenti saat nums[i] > 0 dan lewati i jika nums[i] sama dengan nums[i-1].
Mulai dengan set kosong. Untuk setiap j mulai dari i+1, hitung need = -nums[i] - nums[j]. Jika need ada di dalam set, catat [nums[i], need, nums[j]] dan lanjutkan j melewati salinan nums[j].
Tambahkan nums[j] ke set dan lanjutkan ke j berikutnya.
Balik urutan triplet yang ditemukan untuk i ini, lalu tambahkan ke jawaban.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

Urutkan dan gunakan dua pointer

Intuisi

Tetapkan nums[i], letakkan lo di i+1 dan hi di indeks terakhir. Jika jumlahnya kurang dari 0, nums[lo] tetap terlalu kecil meskipun dipasangkan dengan nilai terbesar yang tersisa, nums[hi], jadi nilainya tidak bisa dipasangkan dengan apa pun yang masih dalam rentang: geser lo ke kanan. Jika jumlahnya lebih dari 0, kasusnya kebalikan: nums[hi] terlalu besar meskipun dipasangkan dengan nilai terkecil yang tersisa, jadi geser hi ke kiri. Setiap langkah membuang satu nilai untuk selamanya tanpa kehilangan triplet, jadi satu i memerlukan paling banyak n langkah dan pencarian memerlukan O(n²), tanpa memori tambahan.

Nilai berulang memerlukan dua aturan. Lewati i jika nilainya sama dengan nilai sebelumnya. Setelah menemukan kecocokan, geser lo melewati salinan nilainya. hi tidak memerlukan aturan: salinan nilai lama nums[hi] kini menghasilkan jumlah lebih dari 0 dan akan menjauh dengan sendirinya. Karena i mengunjungi nilai-nilai berbeda dalam urutan menaik dan lo hanya bergerak ke kanan, triplet yang dihasilkan akan terurut.

Algoritma

Urutkan nums.
Untuk setiap i, berhenti saat nums[i] > 0 dan lewati i saat nums[i] sama dengan nums[i-1].
Tetapkan lo = i+1 dan hi = n-1. Selama lo < hi, jumlahkan nums[i], nums[lo], dan nums[hi].
Jika hasilnya kurang dari 0, geser lo ke kanan. Jika lebih dari 0, geser hi ke kiri.
Jika hasilnya 0, catat triplet, geser kedua penunjuk, lalu geser lo melewati salinan nilai yang digunakannya.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

Jebakan dan kasus tepi

Melewati i saat nums[i] sama dengan nums[i+1]. Pada [-1, -1, 2], hal ini menghilangkan [-1, -1, 2]; bandingkan dengan nums[i-1].
Berhenti saat nums[i] ≥ 0, bukan saat nums[i] > 0. Ini membuat [0, 0, 0] terlewat.
Menghapus pengulangan di akhir. Untuk 3000 angka nol, perulangan mencatat jutaan salinan [0, 0, 0] sebelum ada pembersihan.
Menggunakan satu posisi dua kali. Versi hash-set yang mengisi set dengan seluruh list terlebih dahulu mengubah [-2, 1, 3] menjadi [-2, 1, 1].
Lupa membalik setiap kelompok dalam versi hash-set. Triplet harus diurutkan.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu 3Sum?

Solusi pengurutan dan dua pointer berjalan dalam waktu O(n²): pengurutan membutuhkan O(n log n), dan masing-masing dari n pilihan nilai pertama memerlukan satu pemindaian O(n). Solusi ini membutuhkan ruang tambahan O(1), di luar pengurutan dan output. Memeriksa setiap tripel membutuhkan O(n³).

Haruskah saya menggunakan two pointers atau hash set untuk 3Sum?

Keduanya berjalan dalam waktu O(n²). Two pointers tidak memerlukan memori tambahan dan memberikan triplet yang sudah berurutan. Hash set memerlukan memori O(n) dan perlu penanganan khusus agar posisi tetap berbeda dan output terurut. Ide hash set penting saat kamu tidak bisa mengurutkan, seperti pada Two Sum, ketika kamu mengembalikan indeks asli.

Bisakah 3Sum diselesaikan lebih cepat daripada O(n²)?

Tidak terlalu jauh. Algoritma terbaik yang diketahui hanya mengungguli n² dengan beberapa faktor logaritmik, dan banyak hasil tentang batas kesulitan dalam geometri komputasional mengasumsikan bahwa tidak ada algoritma yang mencapai pangkat n di bawah 2. O(n²) adalah jawaban yang diharapkan dalam wawancara.

def threeSum(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

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

Output yang diharapkan

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

3Sum

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Coba setiap tripel

Perbaiki satu nilai, temukan pasangannya dengan hash set

Urutkan dan gunakan dua pointer

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa