Two Sum

Q: Berapa kompleksitas waktu Two Sum?

Solusi hash map berjalan dalam waktu O(n) , karena solusi ini mengunjungi setiap angka satu kali dan setiap pencarian atau penyisipan membutuhkan waktu konstan secara rata-rata. Solusi ini menggunakan ruang tambahan O(n) untuk map. Memeriksa setiap pasangan membutuhkan waktu O(n²) dan ruang O(1) .

MudahHashing

+10

Kamu mendapatkan array bilangan bulat nums dan bilangan bulat target. Tepat dua elemen nums pada posisi yang berbeda jika dijumlahkan menghasilkan target. Kembalikan indeks kedua elemen tersebut, dengan indeks yang lebih kecil terlebih dahulu.

Fungsi

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

numsinteger-array: array bilangan bulat yang akan dicari
targetinteger: jumlah yang harus dicapai oleh kedua entri
Mengembalikaninteger-array: kedua indeks, yang lebih kecil terlebih dahulu

Batasan

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
-10⁹ ≤ target ≤ 10⁹
Tepat satu pasangan posisi yang berbeda memiliki jumlah target.

Contoh

Input: nums = [3, 8, 12, 5]target = 17
Output: [2, 3]
Penjelasan: 12 berada di indeks 2 dan 5 di indeks 3, dan 12 + 5 = 17. Tidak ada pasangan lain yang jumlahnya mencapai 17.

Pertanyaan lanjutan

Jika nums sudah terurut, bisakah kamu menemukan pasangan tersebut dalam waktu O(n) dengan hanya O(1) memori tambahan?

Petunjuk

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

0 dari 3 dibuka

Solusi

Memeriksa setiap pasangan bisa dilakukan, tetapi jumlah pekerjaan bertambah seiring kuadrat panjangnya. Balik pertanyaannya: saat berada pada angka x, kamu sudah tahu bahwa pasangannya pasti target - x. Hash map memberitahumu dalam waktu konstan apakah kamu sudah melewati nilai itu, sehingga satu kali penelusuran sudah cukup.

Periksa setiap pasangan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Tetapkan satu indeks awal i, lalu coba setiap indeks j di sebelah kanannya sampai nums[i] + nums[j] sama dengan target. Memulai j dari i + 1 mencegah suatu posisi dipasangkan dengan dirinya sendiri, mencoba setiap pasangan satu kali, dan menempatkan indeks yang lebih kecil terlebih dahulu. Pasangan yang kamu cari termasuk salah satu pasangan yang kamu coba, jadi kamu akan menemukannya.

n angka membentuk sekitar n²/2 pasangan: n = 10^4 berarti hampir 5 × 10^7 penjumlahan.

Algoritma

Lakukan perulangan i pada setiap indeks nums.
Untuk setiap i, lakukan perulangan j dari i + 1 hingga indeks terakhir.
Jika nums[i] + nums[j] sama dengan target, kembalikan [i, j].
Jika kedua perulangan selesai, kembalikan array kosong. Soal ini menjamin hal tersebut tidak akan terjadi.

def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        # Only look at partners to the right, so each pair is checked once.
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Satu kali iterasi dengan hash map

Intuisi

Untuk nums[i] yang tetap, perulangan bagian dalam pada pendekatan brute force mencari satu nilai yang sudah kamu ketahui sebelumnya: target - nums[i]. Pemindaian itu sebenarnya adalah pencarian, dan hash map yang memetakan nilai ke indeks melakukan pencarian dalam waktu konstan secara rata-rata.

Cari terlebih dahulu, simpan setelahnya. Dengan begitu, sebuah angka hanya bisa dipasangkan dengan angka yang muncul sebelumnya, tidak pernah dengan dirinya sendiri, dan karena pasangannya selalu muncul lebih awal, indeksnya berada di urutan pertama. Setiap angka dikunjungi sekali dengan operasi map yang membutuhkan waktu konstan, jadi pencariannya berkompleksitas O(n); biayanya adalah map dengan hingga n entri.

Algoritma

Buat map kosong dari nilai ke indeks.
Untuk setiap indeks i, hitung need, nilai yang melengkapi pasangan: target dikurangi nums[i].
Jika need ada di dalam map, kembalikan indeks yang tersimpan, diikuti i.
Jika tidak, simpan nums[i] dengan indeks i, lalu lanjutkan.

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

Jebakan dan kasus tepi

Menyimpan angka sebelum mencari pasangannya. Dengan [4, 2, 6] dan target = 8, angka 4 menemukan dirinya sendiri dan kamu mengembalikan [0, 0].
Mengembalikan indeks dalam urutan yang salah. Jika pencarian dilakukan sebelum penyimpanan, indeks dari map adalah yang lebih kecil dan harus diletakkan lebih dulu.
Mengurutkan array untuk menggunakan dua pointer, lalu mengembalikan posisi dari salinan yang sudah diurutkan. Simpan indeks asli di samping setiap nilai.
Mengasumsikan nilainya positif atau berbeda. [0, 7, -3, 0] dengan target = 0 memasangkan kedua angka nol: [0, 3].
Dalam Lua dan R, mengembalikan indeks berbasis 1. Kurangi masing-masing dengan 1.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Two Sum?

Solusi hash map berjalan dalam waktu O(n), karena solusi ini mengunjungi setiap angka satu kali dan setiap pencarian atau penyisipan membutuhkan waktu konstan secara rata-rata. Solusi ini menggunakan ruang tambahan O(n) untuk map. Memeriksa setiap pasangan membutuhkan waktu O(n²) dan ruang O(1).

Bisakah Two Sum diselesaikan tanpa ruang tambahan?

Tidak dalam waktu linear pada array yang tidak terurut. Dengan ruang tambahan O(1), kamu kembali harus memeriksa setiap pasangan, yang membutuhkan waktu O(n²). Hash map menukar penggunaan memori O(n) dengan waktu linear.

Bagaimana Two Sum menangani angka duplikat?

Duplikat berfungsi saat kamu mencari pasangannya sebelum menyimpan angka saat ini. Dalam [7, 3, 7] dengan target = 14, angka 7 pertama disimpan pada indeks 0 dan angka 7 kedua menemukannya, sehingga menghasilkan [0, 2]. Satu angka 7 saja tidak pernah berpasangan dengan dirinya sendiri: angka itu belum ada di map saat kamu mencarinya.

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

Tes #1

Tes #2

Tes #3

Argumen

nums = [3, 8, 12, 5]
target = 17

Output yang diharapkan

[2, 3]