Two-Sum dan Berbagai Variasinya
Selesaikan two-sum, three-sum, four-sum, dan two-sum dengan array terurut menggunakan hash map serta dua pointer, sambil membandingkan biaya waktu dan ruang.
Two-Sum dan Berbagai Variasinya adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Jumlah Dua: Masalah Wawancara Klasik
LeetCode 1 'Jumlah Dua': diberikan larik tak terurut dan target, kembalikan indeks dua elemen yang jumlahnya sama dengan target. Pendekatan coba semua pasangan memiliki kompleksitas O(n²). Pendekatan optimal O(n) menggunakan peta hash: untuk setiap elemen x, periksa apakah target - x sudah ada di dalam peta. Jika ya, kembalikan pasangan indeks tersebut. Jika tidak, simpan x dan indeksnya di dalam peta.
Jumlah Dua sering menjadi masalah pertama dalam wawancara — menguasainya dengan baik menunjukkan bahwa Anda siap menghadapi masalah yang lebih sulit.
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]Mengapa Peta Hash Berfungsi untuk Jumlah Dua
Peta hash menyimpan setiap elemen yang telah diproses. Saat memproses elemen x, jika target - x ada di dalam peta, kedua elemen tersebut membentuk pasangan yang valid. Yang penting, nilai pelengkap selalu diperiksa sebelum x disimpan. Hal ini mencegah satu elemen dipasangkan dengan dirinya sendiri (misalnya, jika x == target/2, pemeriksaan peta dilakukan sebelum x disimpan, sehingga tidak akan cocok kecuali terdapat dua salinan).
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = iJumlah Dua pada Larik Terurut (Dua Penunjuk)
Jika larik sudah terurut dan Anda memerlukan indeks nilai (bukan indeks asli), gunakan teknik dua penunjuk: penunjuk kiri dan kanan dimulai dari ujung yang berlawanan. Jika jumlah sama dengan target, kembalikan hasilnya. Jika jumlah terlalu kecil, geser penunjuk kiri ke kanan. Jika jumlah terlalu besar, geser penunjuk kanan ke kiri. Waktu yang diperlukan adalah O(n) dan ruangnya O(1) — lebih baik daripada pendekatan peta hash ketika larik sudah terurut dan memori terbatas.
def twoSumSorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed as per LeetCode 167
elif s < target:
lo += 1
else:
hi -= 1
return []
print(twoSumSorted([2, 7, 11, 15], 9)) # [1, 2]
print(twoSumSorted([2, 3, 4], 6)) # [1, 3]
print(twoSumSorted([-1, 0], -1)) # [1, 2]Jumlah Tiga (LeetCode 15)
LeetCode 15 'Jumlah Tiga': temukan semua triplet unik yang jumlahnya nol. Urutkan larik, tetapkan satu elemen setiap kali, lalu terapkan teknik dua penunjuk pada sublarik terurut yang tersisa. Lewati nilai duplikat untuk menghindari triplet duplikat. Waktu: O(n²) — optimal untuk masalah ini karena keluarannya sendiri dapat memiliki O(n²) triplet.
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicates
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0])) # [[0,0,0]]Jumlah Empat (LeetCode 18)
LeetCode 18 'Jumlah Empat': temukan semua kuadruplet unik yang jumlahnya sama dengan target. Perluas Jumlah Tiga: tetapkan dua elemen menggunakan dua perulangan bertingkat (dengan melewati duplikat), lalu terapkan teknik dua penunjuk pada sublarik bagian dalam. Waktu: O(n³). Untuk jumlah-k secara umum, polanya melakukan rekursi sebanyak k-2 kali lalu menerapkan dua penunjuk, sehingga waktunya O(n^(k-1)).
def fourSum(nums, target):
nums.sort()
n, result = len(nums), []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
lo, hi = j+1, n-1
while lo < hi:
s = nums[i]+nums[j]+nums[lo]+nums[hi]
if s == target:
result.append([nums[i],nums[j],nums[lo],nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return result
print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]Jumlah Dua Terdekat dengan Target
Varian yang umum: temukan pasangan dengan jumlah yang paling dekat dengan target (tidak harus sama persis dengan target). Urutkan larik dan gunakan dua penunjuk. Lacak jumlah terdekat yang telah ditemukan dan perbarui setiap kali Anda menemukan pasangan dengan selisih absolut yang lebih kecil dari target. Pendekatan O(n log n) ini mudah diterapkan setelah pengurutan.
def twoSumClosest(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
best = float('inf')
best_pair = None
while lo < hi:
s = nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
best_pair = (nums[lo], nums[hi])
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
return best_pair # exact match
return best_pair
print(twoSumClosest([1, 3, 4, 7, 10], 15)) # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10)) # (2, 8) => 10, exact!Jumlah Dua dengan Banyak Pasangan (Semua Pasangan)
Untuk menemukan semua pasangan yang jumlahnya sama dengan target, urutkan larik dan gunakan dua penunjuk sambil mengumpulkan semua pasangan. Setelah menemukan pasangan yang valid, lewati duplikat dari kedua ujung sebelum melanjutkan. Pengurutan memerlukan O(n log n) dan pemindaian memerlukan O(n), sehingga keseluruhannya O(n log n). Menggunakan peta hash untuk mengumpulkan pasangan juga valid, tetapi perlu berhati-hati dalam menangani duplikat.
def twoSumAllPairs(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
pairs = []
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
pairs.append((nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return pairs
print(twoSumAllPairs([1,1,2,3,4,4,5], 5)) # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]Menghitung Pasangan dengan Jumlah Kurang dari K
Varian lainnya adalah menghitung jumlah pasangan yang jumlahnya kurang dari k. Urutkan larik dan gunakan dua penunjuk. Saat nums[lo] + nums[hi] < k, semua pasangan (lo, lo+1), (lo, lo+2), ..., (lo, hi) valid — yaitu hi - lo pasangan. Majukan lo. Jika tidak, perkecil hi. Total waktu: O(n log n) untuk pengurutan ditambah O(n) untuk penghitungan.
def countPairsLessThan(nums, k):
nums.sort()
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] < k:
count += hi - lo # all (lo, lo+1)...(lo, hi) are valid
lo += 1
else:
hi -= 1
return count
print(countPairsLessThan([1, 3, 7, 11, 12], 10)) # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7)) # (2,3),(2,3) => 2... verifyJumlah Dua dengan Peta Hash: Menangani Duplikat
Jika nilai yang sama dapat muncul beberapa kali dan Anda perlu menghitung jumlah pasangan yang valid (bukan sekadar memeriksa keberadaannya), simpan frekuensi di dalam peta. Untuk pasangan yang kedua elemennya sama, jumlah pasangan dari frekuensi f adalah f*(f-1)//2. Untuk pasangan dengan dua elemen berbeda, kalikan frekuensinya. Dengan cara ini, semua pasangan valid dapat dihitung dalam O(n).
from collections import Counter
def countTwoSumPairs(nums, target):
freq = Counter(nums)
count = 0
seen = set()
for x in freq:
y = target - x
if y in freq and (x, y) not in seen:
if x == y:
count += freq[x] * (freq[x] - 1) // 2
else:
count += freq[x] * freq[y]
seen.add((x, y))
seen.add((y, x))
return count
print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...Mengenali Variasi Pola Jumlah Dua
Pola Jumlah Dua muncul dalam banyak bentuk terselubung. Kenali pola ini ketika masalah meminta Anda menemukan dua atau lebih elemen yang memenuhi hubungan numerik (jumlah, hasil kali, atau selisih). Strategi intinya selalu sama: tetapkan satu elemen, lalu cari nilai pelengkapnya dalam struktur yang telah dihitung sebelumnya (peta hash atau larik terurut + penunjuk). Perluas ke jumlah-k dengan menetapkan k-2 elemen melalui perulangan bertingkat dan menerapkan kasus dasar.
# Summary of approaches by scenario
scenarios = [
('Unsorted array, any indices, one pair', 'hash map O(n) time O(n) space'),
('Sorted array, any indices, one pair', 'two pointers O(n) time O(1) space'),
('All unique pairs summing to target', 'sort + two pointers O(n log n)'),
('Three numbers summing to zero (3-sum)', 'sort + fix + two pointers O(n^2)'),
('k numbers summing to target (k-sum)', 'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
print(f'{scenario}\n => {approach}\n')Komunikasi Wawancara untuk Jumlah Dua
Ketika Jumlah Dua muncul dalam wawancara, jelaskan pemikiran Anda dengan lantang: 'Saya memerlukan dua bilangan yang jumlahnya sama dengan target. Untuk setiap bilangan x, saya perlu memeriksa apakah target-x ada. Saya dapat menjawabnya dalam O(1) dengan peta hash, sehingga total waktunya O(n) dan ruangnya O(n). Sebagai alternatif, jika larik sudah terurut, saya dapat menggunakan dua penunjuk dengan ruang O(1).' Sampaikan kedua pendekatan tersebut dan tanyakan apakah ada batasan ruang sebelum memilih.
Pemeriksaan Singkat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rekapitulasi Pelajaran
Dalam pelajaran ini Anda mempelajari: dua-jumlah menggunakan peta hash untuk memeriksa keberadaan komplemen dalam O(1), sehingga keseluruhannya O(n), untuk larik terurut, dua penunjuk mencapai penggunaan ruang O(1), dan tiga-jumlah serta empat-jumlah direduksi menjadi dua-jumlah melalui pengurutan dan perulangan bersarang, masing-masing berjalan dalam O(n²) dan O(n³). Selanjutnya kita akan membahas pola penghitungan frekuensi dan pengelompokan dengan defaultdict dan Counter.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Two-Sum dan Berbagai Variasinya” gratis?
Ya — teks lengkap “Two-Sum dan Berbagai Variasinya” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Two-Sum dan Berbagai Variasinya”?
Selesaikan two-sum, three-sum, four-sum, dan two-sum dengan array terurut menggunakan hash map serta dua pointer, sambil membandingkan biaya waktu dan ruang. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 2 dari 4.
Berapa lama pelajaran “Two-Sum dan Berbagai Variasinya” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Internal Fungsi Hash dan Penanganan Tabrakan
- Two-Sum dan Berbagai Variasinya
- Penghitungan Frekuensi dan Pengelompokan
- Urutan Berurutan Terpanjang dan Cache LRU