Sebagian besar pertanyaan wawancara bertema "kerjakan dalam satu kali lintasan" punya jawaban yang sama: ingat apa yang sudah Anda lihat dalam dictionary atau set, dengan kunci yang bisa dicari dalam satu langkah.
- Set elemen yang sudah terlihat: pengulangan pertama, duplikat, "apakah kita sudah pernah menemui ID ini?".
- Pencarian komplemen: untuk dua nilai yang jumlahnya sama dengan target, simpan posisi setiap nilai, dan untuk setiap nilai baru cari
target - value.
- Kunci pengelompokan: letakkan item yang saling terkait di bawah kunci yang sama, seperti anagram di bawah huruf-hurufnya yang diurutkan.
- Hitungan:
Counter menjawab "item pertama yang muncul satu kali" dalam dua kali lintasan.
- Set berisi semua nilai: memungkinkan Anda memulai rangkaian hanya dari nilai pertamanya (
x - 1 tidak ada di dalam set), sehingga rangkaian angka berurutan terpanjang cukup O(n).
Keahliannya ada pada pemilihan kunci. Tanyakan pada diri sendiri: apa yang perlu saya temukan seketika saat item berikutnya datang?
Output: (1, 3). Saat 9 masuk, pasangannya, 7, sudah ada di dictionary.