Two Pointer Technique

Ikki ko'rsatkich texnikasi

Ikki kishi bitta kitobning ikki uchidan (biri boshidan, biri oxiridan) o'qib, o'rtada uchrashishini tasavvur qiling — bu ikkalasi alohida-alohida boshidan boshlab o'qishdan tezroq. Two Pointer (ikki ko'rsatkich) texnikasi — aynan shu g'oya: bitta ro'yxatda ikkita "ko'rsatkich"ni (indeksni) turli tomondan yoki turli tezlikda yurgizib, muammoni bitta aylanishda hal qilish.

Bu texnika ayniqsa saralangan ro'yxatda ishlaganda kuchli: masalan, "ro'yxatda yig'indisi berilgan songa teng bo'lgan ikkita son bormi?" degan savolga javob berish uchun, ikkita ichma-ich sikl (O(n²)) o'rniga, ikkita ko'rsatkich bilan O(n)da javob berish mumkin.

example.go

package main

import "fmt"

func hasPairWithSum(nums []int, target int) bool {
	left, right := 0, len(nums)-1
	for left < right {
		sum := nums[left] + nums[right]
		if sum == target {
			return true
		}
		if sum < target {
			left++ // yig'indi kichik — chapdagi ko'rsatkichni kattaroq tomonga siljitamiz
		} else {
			right-- // yig'indi katta — o'ngdagi ko'rsatkichni kichikroq tomonga siljitamiz
		}
	}
	return false
}

func main() {
	nums := []int{1, 2, 4, 7, 11, 15}
	fmt.Println(hasPairWithSum(nums, 15)) // 4 + 11
	fmt.Println(hasPairWithSum(nums, 20))
}

left chapdan, right o'ngdan boshlanadi. Ro'yxat saralangan bo'lgani uchun, biz aqlli qaror qabul qila olamiz: agar joriy yig'indi kerakli sondan kichik bo'lsa, uni kattalashtirish uchun leftni o'ngga siljitamiz (kattaroq songa o'tish); agar yig'indi katta bo'lsa, rightni chapga siljitib, kichikroq songa o'tamiz. Bu — har safar noto'g'ri natijani berib turgan variantlardan birini butunlay olib tashlash, xuddi Binary Search'dagi kabi "aqlli qisqartirish".

left < right sharti bilan ikkalasi "uchrashguncha" davom etamiz — bu jarayon har bir elementni ko'pi bilan bir marta ko'radi, shuning uchun umumiy vaqt O(n), O(n²)ning ichma-ich sikli o'rniga.

>_ Exercise

Palindrom (old-orqa bir xil o'qiladigan) matnni Two Pointer bilan tekshiring.

•isPalindrome(s string) bool yozing: left=0, right=len(s)-1 dan boshlab, har ikki tomondagi harflarni solishtiring
•mos kelmasa false, ko'rsatkichlar uchrashguncha davom etsa true qaytaring
•"level" va "hello" uchun natijalarni chop eting

Stuck? Reveal a hint to help you.

Hints (0/3)

Key Takeaway

Key Takeaway:

Two Pointer texnikasi ikkita indeksni turli tomondan yurgizib, saralangan yoki simmetrik ma'lumotdagi muammolarni ichma-ich sikldan (O(n²)) tezroq, bitta aylanishda (O(n)) hal qiladi.

NEXT UP

Algorithms Quiz

OUTPUT

$ go run main.go
Kodingizni ishga tushiring