Two Sum II: Sorted Input

Q: Apa kompleksitas waktu dari Two Sum II?

Solusi dua pointer berjalan dalam waktu O(n) dan menggunakan ruang ekstra O(1) : setiap langkah menggerakkan satu pointer ke arah dalam, dan keduanya bertemu setelah paling banyak n-1 langkah. Melakukan pencarian biner untuk setiap pasangan membutuhkan waktu O(n log n) , dan memeriksa setiap pasangan membutuhkan waktu O(n²) .

Q: Mengapa tidak menggunakan hash map seperti pada Two Sum pertama?

Hash map juga berfungsi dan berjalan dalam waktu O(n) , tetapi menyimpan hingga n nilai. Urutan yang terurut membuat penggunaan memori itu tidak perlu: kedua pointer tahu harus bergerak ke arah mana hanya dari jumlahnya. Pewawancara menanyakan versi ini untuk melihat apakah kamu memanfaatkan urutan yang diberikan.

MudahTwo pointers Binary search

+10

Kamu mendapatkan array bilangan bulat numbers yang diurutkan dalam urutan tidak menurun, dan sebuah bilangan bulat target. Tepat satu pasangan posisi berbeda memiliki dua nilai yang jika dijumlahkan hasilnya target. Kembalikan kedua posisi tersebut sebagai indeks berbasis 0, dengan indeks yang lebih kecil terlebih dahulu.

Fungsi

twoSumSorted(numbers: integer-array, target: integer) → integer-array

numbersinteger-array: array bilangan bulat yang sudah diurutkan
targetinteger: jumlah yang harus dicapai oleh kedua nilai
Mengembalikaninteger-array: dua indeks berbasis 0 [i, j] dengan i < j dan numbers[i] + numbers[j] == target

Batasan

2 ≤ numbers.length ≤ 10⁴
-5 × 10⁸ ≤ numbers[i] ≤ 5 × 10⁸
-10⁹ ≤ target ≤ 10⁹
numbers diurutkan dalam urutan tidak menurun.
Tepat satu pasangan indeks i < j memiliki numbers[i] + numbers[j] == target.

Contoh

Input: numbers = [-4, 1, 3, 8, 12]target = 9
Output: [1, 3]
Penjelasan: 1 berada pada indeks 1 dan 8 pada indeks 3, dan 1 + 8 = 9. Tidak ada pasangan lain yang hasilnya 9: misalnya, -4 + 12 = 8.

Pertanyaan lanjutan

Bisakah kamu menyelesaikannya dalam waktu O(n) dengan memori tambahan O(1)?

Petunjuk

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

0 dari 3 dibuka

Solusi

array sudah diurutkan, dan urutan itu memberi tahu kamu harus bergerak ke arah mana. Letakkan satu penunjuk di setiap ujung. Jika jumlahnya terlalu kecil, hanya nilai kiri yang lebih besar yang bisa membantu; jika terlalu besar, hanya nilai kanan yang lebih kecil yang bisa membantu. Setiap langkah menyingkirkan satu nilai selamanya, jadi satu kali pemindaian menemukan pasangannya tanpa memori tambahan.

Periksa setiap pasangan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Coba setiap pasangan posisi i < j dan uji apakah numbers[i] + numbers[j] sama dengan target. Karena j dimulai tepat setelah i, pasangan yang kamu temukan memiliki indeks yang lebih kecil terlebih dahulu.

Cara ini mengabaikan urutan yang sudah diurutkan. Dengan n = 10^4, ada sekitar 5 × 10^7 pasangan, dan jika jawaban berada di dekat akhir array, kamu harus menguji hampir semuanya.

Algoritma

Lakukan perulangan pada i untuk setiap indeks.
Lakukan perulangan pada j dari i+1 hingga indeks terakhir.
Jika numbers[i] + numbers[j] sama dengan target, kembalikan [i, j].

def twoSumSorted(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i, j]
    return []

Pencarian biner untuk setiap pasangan

Intuisi

Setelah kamu menetapkan numbers[i], pasangannya adalah tepat target - numbers[i]. Rentang di sebelah kanan i sudah terurut, jadi pencarian biner memberi tahu dalam O(log n) langkah apakah pasangannya ada di sana. Pencarian hanya di sebelah kanan membuat indeks yang lebih kecil berada di urutan pertama dan mencegah suatu nilai berpasangan dengan dirinya sendiri. Karena pasangannya unik, setiap kecocokan adalah jawabannya.

Pada contoh pertama, i = 0 membutuhkan 13, tetapi nilai itu tidak ada; i = 1 membutuhkan 8, yang ditemukan pada indeks 3. Itu berarti melakukan n pencarian, masing-masing sebanyak O(log n).

Algoritma

Lakukan perulangan i dari 0 hingga n-2.
Hitung need = target - numbers[i].
Lakukan pencarian biner untuk need pada indeks i+1 hingga n-1.
Jika kamu menemukannya di mid, kembalikan [i, mid].

def twoSumSorted(numbers, target):
    n = len(numbers)
    for i in range(n - 1):
        need = target - numbers[i]
        lo, hi = i + 1, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if numbers[mid] == need:
                return [i, mid]
            if numbers[mid] < need:
                lo = mid + 1
            else:
                hi = mid - 1
    return []

Dua pointer dari kedua ujung

Intuisi

Perhatikan numbers[left] + numbers[right]. Jika hasilnya terlalu kecil, numbers[left] tidak mungkin menjadi bagian dari jawaban: bahkan jika dipasangkan dengan nilai terbesar yang masih dipertimbangkan, hasilnya tetap kurang. Jika hasilnya terlalu besar, numbers[right] tetap terlalu besar meski dipasangkan dengan nilai terkecil yang tersisa. Jadi, setiap langkah membuang nilai yang tidak mungkin menjadi bagian dari pasangan, bukan pasangan itu sendiri. Pointer akan mencapainya setelah paling banyak n-1 langkah, dengan dua variabel.

Pada [-4, 1, 3, 8, 12] dengan target = 9: -4 + 12 = 8 terlalu kecil, jadi left berpindah ke indeks 1. Lalu 1 + 12 = 13 terlalu besar, jadi right berpindah ke indeks 3. Sekarang 1 + 8 = 9, dan jawabannya adalah [1, 3].

Algoritma

Atur left ke 0 dan right ke n-1.
Selama left < right, hitung total = numbers[left] + numbers[right].
Jika total sama dengan target, kembalikan [left, right].
Jika total lebih kecil, tambahkan 1 ke left; jika lebih besar, kurangi 1 dari right.

def twoSumSorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1  # need a bigger sum
        else:
            right -= 1  # need a smaller sum
    return []

Jebakan dan kasus tepi

Mengembalikan posisi berbasis 1. Untuk [-4, 1, 3, 8, 12] dan target = 9, jawabannya adalah [1, 3], bukan [2, 4]. Di Lua dan R, kurangi 1 sebelum mengembalikan hasil.
Melakukan perulangan dengan left <= right. Saat kedua pointer bertemu, jumlahnya menggunakan satu nilai dua kali.
Menggerakkan pointer yang salah. Jumlah yang terlalu kecil membutuhkan nilai yang lebih besar, dan hanya left yang bisa memberikan nilai tersebut.
Menolak nilai duplikat. [2, 2, 5, 7] dengan target = 4 menggunakan kedua angka 2, yang berada di posisi berbeda.

Pertanyaan yang sering diajukan3

<p>Apa kompleksitas waktu dari Two Sum II?</p>

Solusi dua pointer berjalan dalam waktu O(n) dan menggunakan ruang ekstra O(1): setiap langkah menggerakkan satu pointer ke arah dalam, dan keduanya bertemu setelah paling banyak n-1 langkah. Melakukan pencarian biner untuk setiap pasangan membutuhkan waktu O(n log n), dan memeriksa setiap pasangan membutuhkan waktu O(n²).

Mengapa tidak menggunakan hash map seperti pada Two Sum pertama?

Hash map juga berfungsi dan berjalan dalam waktu O(n), tetapi menyimpan hingga n nilai. Urutan yang terurut membuat penggunaan memori itu tidak perlu: kedua pointer tahu harus bergerak ke arah mana hanya dari jumlahnya. Pewawancara menanyakan versi ini untuk melihat apakah kamu memanfaatkan urutan yang diberikan.

Kapan pencarian biner menjadi pilihan yang lebih baik di sini?

Ketika satu nilai sudah ditentukan dan kamu hanya perlu mencari pasangannya. Jika numbers[0] harus ada dalam pasangan, satu pencarian biner akan menemukan indeks lainnya dalam O(log n). Untuk menemukan pasangan yang belum diketahui, pemindaian dengan dua pointer lebih cepat daripada n pencarian terpisah.

def twoSumSorted(numbers, target):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

numbers = [-4, 1, 3, 8, 12]
target = 9

Output yang diharapkan

[1, 3]

Two Sum II: Sorted Input

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Periksa setiap pasangan

Pencarian biner untuk setiap pasangan

Dua pointer dari kedua ujung

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa