1. Two Sum

# 1. Two Sum> [!NOTE]> **Masala:** [LeetCode 1 — Two Sum](https://leetcode.com/problems/two-sum/description/). Masala **bir necha usulda** yechiladi — eng oddiysidan optimaligacha, har biri: ğoya → algoritm → kod → murakkablik → kamchiligi. Körsatmalarni öz matningiz bilan almashtiring; yechim kerakli miqdorda bölsin (kamida ikkita).## Masala*Shartni öz sözlaringiz bilan 2–3 jumlada yozing:* **nima beriladi** va **nima qaytarilishi kerak**.**Cheklovlar:**- `1 <= n <= 10^4`- Qiymatlar oraliği: …> [!TIP]> **Cheklovlar nima deydi:** bir soniyada taxminan $10^8$ oddiy amal. $n \le 20$ — $O(2^n)$ ham ötadi; $n \le 10^3$ — $O(n^2)$; $n \le 10^5$ — $O(n \log n)$ yoki $O(n)$ kerak. Shu bilan qaysi yechim *yetarli* ekanini oldindan biling.## Misollar### 1-misol```textKirish:  …Chiqish: …```**Nega:** natija qanday hosil bölishini bir qatorda körsating.### 2-misol — chegaraviy holat```textKirish:  …Chiqish: …```**Nega:** bu misol qaysi chekka holatni tekshiradi.## Ğoyaga yölKod yozishdan oldin — fikrlash. Quyidagi savollarga qisqa javob yozing:1. **Qölda yeching.** 1-misolni qoğozda yechganda nimani qildingiz? Shu harakatlar — birinchi algoritm.2. **Eng oddiy usul qaysi?** Odatda hamma variantni tekshirish — bu 1-yechim, u töğri, lekin sekin bölishi mumkin.3. **Qaysi ish takrorlanadi?** Sekin usulda bir xil hisob qayta-qayta bajariladimi? Ana shu takror — tezlashtirish joyi.4. **Qaysi naqsh mos?** Hash jadval, ikki körsatkich, sirpanuvchi oyna, binar qidiruv, stek, DP, graf aylanishi …**Yechimlar xaritasi:**| # | Yondashuv | Vaqt | Xotira | Qachon tanlash || :---: | :--- | :---: | :---: | :--- || 1 | Hamma variantni tekshirish | $O(\dots)$ | $O(\dots)$ | birinchi, töğriligi aniq yechim || 2 | … | $O(\dots)$ | $O(\dots)$ | … || 3 | … **(tavsiya)** | $O(\dots)$ | $O(\dots)$ | … |## 1-yechim: Hamma variantni tekshirish### ĞoyaEng töğridan-töğri usul: masala nimani sörasa, shuni harfma-harf bajarish.### Algoritm1. …2. …### Kod```go// solveBrute — … (eng oddiy, töğriligi aniq usul).func solveBrute(nums []int) int {	return 0}```### Murakkablik**Vaqt** $O(\dots)$ — nega; **xotira** $O(\dots)$ — nega.### KamchiligiQaysi ish behuda takrorlanadi? Shu kuzatuv keyingi yechimga olib keladi.## 2-yechim: …### Ğoya1-yechimning kamchiligini qanday tuzatamiz — bir-ikki jumlada.### Algoritm1. …2. …### Kod```go// solveBetter — … .func solveBetter(nums []int) int {	return 0}```### Murakkablik**Vaqt** $O(\dots)$; **xotira** $O(\dots)$.### KamchiligiHali nimasi ortiqcha? (Kerak bölmasa, bu bölimni olib tashlang.)## 3-yechim: … (tavsiya)### Ğoya> [!TIP]> **Asosiy ğoya:** yechimni bitta jumlada ayting — butun algoritm shu kuzatuvdan kelib chiqadi.### Algoritm1. …2. …3. …### Kod```go// solve — … (tavsiya etilgan yechim).func solve(nums []int) int {	// 1-qadam: …	// 2-qadam: …	return 0}```### Qadam-baqadam tahlil1-misolni qölda bajaring: har qadamdan keyingi özgaruvchilar holati. Kod notöğri ishlasa, xato aynan shu jadvaldagi qatorda körinadi.| Qadam | Element | Holat | Izoh || :---: | :--- | :--- | :--- || 1 | … | … | … || 2 | … | … | natija: … |### Murakkablik**Vaqt** $O(\dots)$ — nega; **xotira** $O(\dots)$ — nega.## TaqqoslashBir xil kirishda (eng yomon holat, $n = 10^4$) yechimlarni `go test -bench .` bilan ölchang:| Yechim | Vaqt | Xotira | $n = 10^4$ da || :--- | :---: | :---: | ---: || 1-yechim | $O(\dots)$ | $O(\dots)$ | … || 2-yechim | $O(\dots)$ | $O(\dots)$ | … || 3-yechim | $O(\dots)$ | $O(\dots)$ | … |> [!IMPORTANT]> **Intervyuda:** avval 1-yechimni ayting (töğri ekanini körsatadi), uning kamchiligini nomlang, keyin optimal yechimga öting — fikrlash yöli javobning özi kabi muhim.## Chegaraviy holatlarHar birini testda tekshirib, belgilab qöying:- [ ] Eng kichik kirish (bösh yoki bitta element)- [ ] Takroriy qiymatlar- [ ] Manfiy sonlar va nol- [ ] Eng katta kirish (cheklov chegarasi) — vaqt va xotira yetadimi?> [!WARNING]> **Tez-tez uchraydigan xato:** … (masalan, indeks chegaradan chiqishi, elementni özi bilan juftlash yoki natijani tartiblashni unutish).## TestlarHamma yechim **bir xil** testdan ötishi shart — ular bir-birini tekshiradi. `go test -v` bilan lokal ishga tushiring:```go// Har bir yechim bir xil holatlarda sinovdan ötadi.var solutions = map[string]func(nums []int) int{	"1-yechim": solveBrute,	"2-yechim": solveBetter,	"3-yechim": solve,}func TestSolve(t *testing.T) {	tests := []struct {		name string		nums []int		want int	}{		{"1-misol", []int{ /* … */ }, 0},		{"2-misol: chegaraviy", []int{ /* … */ }, 0},		{"bitta element", []int{1}, 0},	}	for name, f := range solutions {		for _, tt := range tests {			t.Run(name+"/"+tt.name, func(t *testing.T) {				if got := f(tt.nums); got != tt.want {					t.Errorf("%s(%v) = %v, kutilgan %v", name, tt.nums, got, tt.want)				}			})		}	}}```## Murakkablik- **Vaqt:** $O(n)$- **Xotira:** $O(1)$*Tavsiya etilgan yechim uchun.* Nega aynan shunday — har bir element necha marta köriladi va qancha qöshimcha xotira kerak, bir jumlada.## Xulosa- **Asosiy saboq:** masalani qaysi kuzatuv hal qildi — bir jumlada.- **Naqsh:** … — u qachon ishlaydi.- **Öxshash masalalar:** … , … , … .- **Özingizni sinang:** shartni biroz özgartiring (masalan, kirish saralangan bölsa yoki bir nechta javob kerak bölsa) — qaysi yechim qanday özgaradi?