Kalıp #06
Hashing
TemelOrtalama O(1) bakış, frekans sayımı, gruplama ve tümleyen kontrolleri.
Ne zaman kullanılır
Hızlı üyelik, sayım veya türetilmiş anahtarla gruplama gerektiğinde; özellikle iç içe döngü O(n²) olacaksa.
Tanıma ipuçları
- Two sum / hedefe tümleyen
- Anagram / frekans eşitliği
- İmzaya göre grupla (sıralı string, sayım demeti)
- İlk tekil, yinelenenler, en uzun ardışık (set)
Yaygın tuzaklar
- Set/map yerine list kullanmak (O(n) bakış)
- Değişken anahtarlar veya kararsız imzalar
- Hash çarpışması nadir; anahtar tasarımındaki mantık hataları yaygın
90 saniyelik tanıma egzersizi
Hangisi en iyi uyuyor?
- Two sum / hedefe tümleyen
- Anagram / frekans eşitliği
- İmzaya göre grupla (sıralı string, sayım demeti)
Interactive
Zihinsel model
Değişmezin tam adım adım anlatımı. Duraklat, noktalara tıkla veya ← → kullan. Her adımı kendi cümlelerinle anlatmayı hedefle.
Adım 1 / 8
2
7
11
15
map{ }
target = 9
Two Sum in one pass: ask for the complement before inserting.
Nasıl düşünülür
Zaman için alandan feragat et: gördüklerini (veya ihtiyacın olanı) bir sonraki kontrolü O(1) yapan bir anahtar altında sakla.
| Yapı | Kullanım |
|---|---|
Set |
üyelik, ardışık diziler |
Map değer → indeks |
tümleyen / two-sum |
Map anahtar → sayım |
frekanslar, anagramlar |
Map anahtar → liste |
anagram grupla / kova |
Karmaşıklık temeli
Ortalama O(n) zaman, O(n) alan. En kötü hash davranışı nadiren mülakat odağıdır; doğru anahtar tasarımı öyledir.
Şablon
TypeScript, Python ve C#’te aynı iskelet. Değişmezi uyarla; yapıyı koru.
Hashing · Şablon
/** Hashing template: Two Sum with a value→index map. */
export function twoSum(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i]!;
if (seen.has(need)) return [seen.get(need)!, i];
seen.set(nums[i]!, i);
}
throw new Error("No solution");
}
/** Hashing template: Two Sum with a value→index map. */
export function twoSum(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i]!;
if (seen.has(need)) return [seen.get(need)!, i];
seen.set(nums[i]!, i);
}
throw new Error("No solution");
}
#DurumProblemTürZorlukBitti
- 1#1 Two SumRehbereasy
- 2#49 Group AnagramsRehbermedium
- 3#128 Longest Consecutive SequenceRehbermedium
- 4#217 Contains DuplicateRehbereasy
- 5#242 Valid AnagramRehbereasy
- 6#347 Top K Frequent ElementsRehbermedium