İki İşaretçi, Kayan Pencere ve Önek Toplamları

Mülakatlarda ve gerçek projelerde karşına çıkan dizi ve string problemlerinin şaşırtıcı bir kısmı aynı kalıba uyar: "şu koşulu sağlayan çifti bul", "şu özelliğe sahip en uzun parçayı bul", "şu aralığın toplamını hızlıca söyle". İlk akla gelen çözüm genellikle iç içe iki döngüdür ve O(n²) sürer. On bin elemanda bu 100 milyon adım demektir. Bu derste göreceğin desenler aynı problemleri çoğu zaman tek geçişte, O(n) zamanda çözer.

Bir kitaptaki bir cümleyi iki parmağınla takip ettiğini düşün: bir parmak cümlenin başında, diğeri sonunda, ikisi ortada buluşana kadar ilerliyor. Ya da tren penceresinden manzaraya bakıyorsun: pencere sabit genişlikte, manzara kayıyor, sen yalnızca pencereye yeni giren ve pencereden çıkan kısmı fark ediyorsun. İki işaretçi ve kayan pencere desenlerinin sezgisi bu kadar basit. Önek toplamları ise bir market fişindeki "ara toplam" satırlarına benzer: her satıra kadar olan toplamı bir kez yazarsan, herhangi iki satır arasındaki harcamayı bir çıkarma işlemiyle bulursun.

Bu dersin sonunda karşılıklı uçlardan ve hızlı/yavaş işaretçi tekniklerini, sabit ve değişken boyutlu kayan pencereyi, önek toplamlarını ve fark dizilerini Go ile uygulayabileceksin. Daha önemlisi, bir problemi okuduğunda hangi desenin işe yarayacağını ve hangisinin yaramayacağını (ör. negatif sayılar varken kayan pencere) gerekçesiyle söyleyebileceksin.

İki işaretçi: karşılıklı uçlar

Bu desende bir işaretçi dizinin başından, diğeri sonundan başlar ve her adımda en az biri ortaya doğru hareket eder. İşaretçiler buluştuğunda iş biter; toplam hareket en fazla n olduğundan zaman O(n)'dir. İşin sırrı, her adımda "hangi işaretçiyi oynatırsam hiçbir doğru cevabı kaçırmam?" sorusunu cevaplayabilmektir.

Sıralı dizide hedef toplamlı çift

Problem: Artan sırada sıralı [1, 3, 4, 6, 8, 11] dizisinde toplamı 10 olan iki eleman var mı?

Kaba kuvvet çözümü tüm çiftleri dener: n(n-1)/2 çift, yani O(n²). Sıralı olmanın getirdiği bilgiyi kullanalım. left en küçük, right en büyük elemanı göstersin:

• Toplam hedeften büyükse, toplamı küçültmenin tek yolu daha küçük bir sağ eleman seçmektir: right--.
• Toplam hedeften küçükse, toplamı büyütmenin tek yolu daha büyük bir sol eleman seçmektir: left++.
• Eşitse cevabı bulduk.

Aşağıdaki görselleştiricide farklı hedef değerler dene ve her adımda işaretçilerden yalnızca birinin hareket ettiğine, hangisinin hareket edeceğine de toplamın hedefle karşılaştırmasının karar verdiğine dikkat et:

package main

import "fmt"

// pairSum, sıralı nums içinde toplamı target olan iki elemanın indekslerini döndürür.
func pairSum(nums []int, target int) (int, int, bool) {
	left, right := 0, len(nums)-1
	for left < right {
		sum := nums[left] + nums[right]
		switch {
		case sum == target:
			return left, right, true
		case sum < target:
			left++ // toplamı büyütmenin tek yolu
		default:
			right-- // toplamı küçültmenin tek yolu
		}
	}
	return 0, 0, false
}

func main() {
	nums := []int{1, 3, 4, 6, 8, 11}
	if i, j, ok := pairSum(nums, 10); ok {
		fmt.Printf("nums[%d] + nums[%d] = %d + %d = 10\n", i, j, nums[i], nums[j])
	}
	_, _, ok := pairSum(nums, 20)
	fmt.Println("toplamı 20 olan çift var mı?", ok)
}

nums[2] + nums[3] = 4 + 6 = 10
toplamı 20 olan çift var mı? false

Neden doğru? Tüm çiftleri bir tablo gibi düşün: satır i, sütun j, hücrede nums[i] + nums[j]. Dizi sıralı olduğu için değerler sağa ve aşağı doğru artar. (left, right) hücresinde toplam hedeften büyükse, right sütunundaki left ve sonrasındaki bütün hücreler de en az bu kadar büyüktür; o sütunun tamamı elenebilir. Toplam küçükse, left satırındaki right ve öncesindeki bütün hücreler de en fazla bu kadar küçüktür; o satır elenebilir. Her adım bir satırı ya da sütunu çöpe atar ve cevabı içeren hücre asla atılmaz.

Geçerli palindrom (Türkçe dostu)

Problem: Bir cümle, harf ve rakam dışındaki karakterler atılıp büyük/küçük harf farkı yok sayıldığında tersten de aynı okunuyor mu? Türkçenin meşhur örneği: "Ey Edip, Adana'da pide ye".

İki işaretçi burada doğal: bir işaretçi baştan, diğeri sondan gelir; harf olmayan karakterlerin üzerinden atlanır ve karşılıklı harfler karşılaştırılır. Türkçe için iki tuzak var:

1. Bayt değil rune: s[i] bir bayt döndürür. ç, ö, ü gibi harfler UTF-8'de iki bayttır; baytları ters sırada karşılaştırırsan "çöç" gibi bir palindromu bile reddedersin. Önce []rune'a çevir.
2. Türkçe büyük/küçük harf: unicode.ToLower('I') sonucu i olur, oysa Türkçede I harfinin küçüğü ı'dır. unicode.TurkishCase.ToLower bu kuralı uygular.

package main

import (
	"fmt"
	"unicode"
)

// isPalindrome harf ve rakam dışındaki karakterleri atlar; lower, büyük/küçük harf dönüşümünü belirler.
func isPalindrome(s string, lower func(rune) rune) bool {
	runes := []rune(s)
	left, right := 0, len(runes)-1
	for left < right {
		switch {
		case !isAlnum(runes[left]):
			left++
		case !isAlnum(runes[right]):
			right--
		case lower(runes[left]) != lower(runes[right]):
			return false
		default:
			left++
			right--
		}
	}
	return true
}

func isAlnum(r rune) bool {
	return unicode.IsLetter(r) || unicode.IsDigit(r)
}

func main() {
	turkish := unicode.TurkishCase.ToLower
	for _, s := range []string{"Ey Edip, Adana'da pide ye", "Kazak", "çöç", "Merhaba", "Ilık kılı"} {
		fmt.Printf("%-28q Türkçe: %-5v  unicode.ToLower: %v\n",
			s, isPalindrome(s, turkish), isPalindrome(s, unicode.ToLower))
	}
}

"Ey Edip, Adana'da pide ye"  Türkçe: true   unicode.ToLower: true
"Kazak"                      Türkçe: true   unicode.ToLower: true
"çöç"                        Türkçe: true   unicode.ToLower: true
"Merhaba"                    Türkçe: false  unicode.ToLower: false
"Ilık kılı"                  Türkçe: true   unicode.ToLower: false

Son satırdaki "Ilık kılı" yapay bir örnek ama farkı net gösteriyor: baştaki I ile sondaki ı Türkçede aynı harfin büyük ve küçük hâlidir. unicode.ToLower ise I'yı i'ye çevirdiği için eşleşmeyi kaçırıyor.

[]rune dönüşümü O(n) ek bellek harcar. Bellek önemliyse utf8.DecodeRuneInString ile baştan, utf8.DecodeLastRuneInString ile sondan rune okuyarak aynı algoritmayı O(1) ek bellekle yazabilirsin.

En çok su alan kap

Problem: height[i], i konumundaki dikey bir çubuğun yüksekliği. İki çubuk ve aradaki zemin bir kap oluşturur; kabın alabileceği su min(height[i], height[j]) × (j - i) kadardır. En büyük değer ne?

[1, 8, 6, 2, 5, 4, 8, 3, 7] için cevap 49'dur (1. ve 8. indeksler: min(8, 7) × 7).

Kaba kuvvet yine O(n²). İki işaretçiyle en geniş kaptan başlarız ve her adımda kısa olan çubuğu içeri doğru hareket ettiririz. Neden kısa olan? Kabın yüksekliğini kısa çubuk belirler. Uzun çubuğu içeri çekersek genişlik azalır, yükseklik ise hâlâ kısa çubukla sınırlıdır; yani alan asla artamaz. Dolayısıyla kısa çubuğun bu genişlikten daha dar hiçbir eşleşmesi mevcut en iyiyi geçemez ve o çubuk güvenle elenebilir.

height: 1  8  6  2  5  4  8  3  7
        L                       R    min(1,7)×8 = 8    kısa olan L → L++
           L                    R    min(8,7)×7 = 49   kısa olan R → R--
           L                 R       min(8,3)×6 = 18   R--
           L              R          min(8,8)×5 = 40   eşit → R--
           ...                       en iyi: 49

package main

import "fmt"

func maxArea(height []int) int {
	best := 0
	left, right := 0, len(height)-1
	for left < right {
		area := min(height[left], height[right]) * (right - left)
		best = max(best, area)
		if height[left] < height[right] {
			left++ // kısa çubuk elenir
		} else {
			right--
		}
	}
	return best
}

func main() {
	fmt.Println(maxArea([]int{1, 8, 6, 2, 5, 4, 8, 3, 7}))
	fmt.Println(maxArea([]int{1, 1}))
	fmt.Println(maxArea([]int{4, 3, 2, 1, 4}))
}

49
1
16

Üç sayının toplamı (3Sum)

Problem: Toplamı 0 olan bütün farklı üçlüleri bul. [-1, 0, 1, 2, -1, -4] için cevap [-1 -1 2] ve [-1 0 1].

Fikir: diziyi sırala, ilk elemanı i ile sabitle ve kalan kısımda hedefi -nums[i] olan çift toplamını iki işaretçiyle ara. Asıl zorluk tekrarları önlemek:

• Aynı değere sahip ikinci bir i aynı üçlüleri yeniden üretir; nums[i] == nums[i-1] ise atla.
• Bir üçlü bulunduktan sonra left ve right'ı, önceki değerleriyle aynı olan elemanların üzerinden geçir.

package main

import (
	"fmt"
	"slices"
)

// threeSum toplamı 0 olan farklı üçlüleri döndürür. nums yerinde sıralanır.
func threeSum(nums []int) [][]int {
	slices.Sort(nums)
	var result [][]int
	for i := 0; i < len(nums)-2; i++ {
		if nums[i] > 0 {
			break // en küçük eleman pozitifse toplam 0 olamaz
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue // aynı ilk eleman aynı üçlüleri üretir
		}
		left, right := i+1, len(nums)-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			switch {
			case sum < 0:
				left++
			case sum > 0:
				right--
			default:
				result = append(result, []int{nums[i], nums[left], nums[right]})
				left++
				right--
				for left < right && nums[left] == nums[left-1] {
					left++
				}
				for left < right && nums[right] == nums[right+1] {
					right--
				}
			}
		}
	}
	return result
}

func main() {
	fmt.Println(threeSum([]int{-1, 0, 1, 2, -1, -4}))
	fmt.Println(threeSum([]int{0, 0, 0, 0}))
	fmt.Println(threeSum([]int{-2, 0, 0, 2, 2}))
}

[[-1 -1 2] [-1 0 1]]
[[0 0 0]]
[[-2 0 2]]

Sıralama O(n log n), dış döngünün her turunda iki işaretçi taraması O(n) sürer. Toplam O(n²); bu problem için bilinen pratik en iyi yaklaşım budur. Aynı kalıp "4Sum" için bir döngü daha ekleyerek O(n³) olur.

Alan karmaşıklığındaki O(log n), sonucu saymazsak sıralamanın kullandığı yığın derinliğidir.

İki işaretçi: hızlı ve yavaş

İkinci desende iki işaretçi aynı yönde ama farklı hızlarda ilerler. En yaygın biçimi okuma/yazma ayrımıdır: fast her elemanı okur, slow ise "tutulacak" bir sonraki elemanın yazılacağı yeri gösterir. Böylece bir dilimi ek bellek kullanmadan yerinde filtreleyebilirsin.

Sıralı dizide tekrarları yerinde silme

Problem: Sıralı bir dilimdeki tekrarları yerinde kaldır ve benzersiz eleman sayısını k döndür; ilk k eleman benzersiz değerleri içersin.

başlangıç:   0  0  1  1  1  2  2  3  3  4
             s  f                              nums[f] == nums[s-1] → yalnızca f ilerler

nums[f]=1 ≠ 0:
             0  1  1  1  1  2  2  3  3  4
                   s     f                     1 yazıldı, s ilerledi

sonuç:       0  1  2  3  4  |  2  2  3  3  4    k = 5 (dikey çizginin sağı önemsiz)

package main

import "fmt"

// removeDuplicates sıralı nums'taki tekrarları yerinde kaldırır ve benzersiz eleman sayısını döndürür.
func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	slow := 1 // bir sonraki benzersiz elemanın yazılacağı konum
	for fast := 1; fast < len(nums); fast++ {
		if nums[fast] != nums[slow-1] {
			nums[slow] = nums[fast]
			slow++
		}
	}
	return slow
}

// moveZeroes sıfır olmayan elemanların sırasını koruyarak sıfırları sona taşır.
func moveZeroes(nums []int) {
	slow := 0
	for fast := range nums {
		if nums[fast] != 0 {
			nums[slow], nums[fast] = nums[fast], nums[slow]
			slow++
		}
	}
}

func main() {
	nums := []int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4}
	k := removeDuplicates(nums)
	fmt.Println(k, nums[:k])

	zeros := []int{0, 1, 0, 3, 12}
	moveZeroes(zeros)
	fmt.Println(zeros)
}

5 [0 1 2 3 4]
[1 3 12 0 0]

İki fonksiyon da aynı değişmezi korur: nums[:slow] her an "şimdiye kadar tutulmaya karar verilen elemanlar"dır. fast asla slow'un gerisine düşmediği için okunmamış bir elemanın üzerine yazılmaz. moveZeroes içindeki takas, sıfırları slow ile fast arasındaki bölgede toplar ve dilimin sonuna doğru iter.

Bağlı listelerde hızlı ve yavaş işaretçi

Aynı fikrin en ünlü uygulaması Floyd'un döngü tespitidir: kaplumbağa her adımda bir, tavşan iki düğüm ilerler. Listede döngü varsa tavşan eninde sonunda kaplumbağayı arkadan yakalar; yoksa listenin sonuna ulaşır. Tavşan listenin sonuna vardığında kaplumbağanın tam ortada olması da bir listenin orta düğümünü tek geçişte bulmayı sağlar. Ayrıntılı uygulama ve ispat için bağlı listeler dersine bak.

Sabit boyutlu kayan pencere

Problem: Bir dükkânın günlük satışları [2, 1, 5, 1, 3, 2]. Art arda gelen 3 günün en yüksek toplam satışı ne?

Saf yaklaşım her başlangıç noktası için k elemanı yeniden toplar: O(n·k). Oysa pencere bir adım kaydığında değişen yalnızca iki elemandır: sağdan biri girer, soldan biri çıkar. Toplamı sıfırdan hesaplamak yerine güncelleriz.

package main

import "fmt"

// maxSumWindow ardışık k elemanın en büyük toplamını ve bu pencerenin başlangıç indeksini döndürür.
func maxSumWindow(nums []int, k int) (best, start int) {
	sum := 0
	for i := range k {
		sum += nums[i]
	}
	best = sum
	for right := k; right < len(nums); right++ {
		sum += nums[right] - nums[right-k] // yeni eleman girer, en eski eleman çıkar
		if sum > best {
			best, start = sum, right-k+1
		}
	}
	return best, start
}

// maxAverage ardışık k elemanın en büyük ortalamasını döndürür.
func maxAverage(nums []int, k int) float64 {
	best, _ := maxSumWindow(nums, k)
	return float64(best) / float64(k)
}

func main() {
	sales := []int{2, 1, 5, 1, 3, 2}
	best, start := maxSumWindow(sales, 3)
	fmt.Printf("en iyi 3 gün: %v, toplam %d\n", sales[start:start+3], best)

	fmt.Printf("en iyi 4 elemanın ortalaması: %.2f\n", maxAverage([]int{1, 12, -5, -6, 50, 3}, 4))
}

en iyi 3 gün: [5 1 3], toplam 9
en iyi 4 elemanın ortalaması: 12.75

Ortalama problemi ayrı bir algoritma gerektirmez: pencere uzunluğu sabit olduğundan en büyük ortalama, en büyük toplamın k'ya bölümüdür. Bu problemde negatif sayıların sorun çıkarmadığına dikkat et; pencere boyutu sabit olduğu için "pencereyi ne zaman daraltmalıyım?" kararı yoktur.

Değişken boyutlu kayan pencere

Pencerenin boyutu sabit değilse iki işaretçiyi şöyle yönetiriz: right her adımda bir eleman ekleyerek pencereyi genişletir; pencere geçersiz hâle gelirse left onu geçerli olana kadar daraltır. Her eleman pencereye bir kez girer ve en fazla bir kez çıkar. İç içe döngü görsen de toplam iş O(n)'dir.

Aşağıdaki görselleştiricide sağ ucun her adımda ilerlediğini, sol ucun ise yalnızca koşul bozulduğunda hareket ettiğini izle. Pencere hiçbir zaman geriye doğru kaymıyor:

Şablon: sağı genişlet, solu daralt

İki klasik varyant var. "En uzun geçerli pencere" arıyorsan, geçersizken daraltır, sonra cevabı güncellersin. "En kısa geçerli pencere" arıyorsan, geçerli oldukça cevabı güncelleyip daraltırsın:

// En UZUN geçerli pencere
left := 0
for right := range len(nums) {
	add(nums[right]) // pencereye ekle
	for !valid() {
		remove(nums[left]) // pencere geçerli olana kadar soldan çıkar
		left++
	}
	best = max(best, right-left+1)
}

// En KISA geçerli pencere
left = 0
for right := range len(nums) {
	add(nums[right])
	for valid() {
		best = min(best, right-left+1) // geçerliyken kaydet, sonra daralt
		remove(nums[left])
		left++
	}
}

Şablonun çalışması için koşulun monoton olması gerekir: geçerli bir pencereyi genişletmek (en uzun varyantında) ya da geçersiz bir pencereyi daraltmak onu "daha kötü" yapmamalıdır. Bu özellik yoksa desen yanlış sonuç verir; aşağıda önek toplamlarında bunun somut bir örneğini göreceksin.

Tekrarsız en uzun alt string

Problem: Hiçbir karakteri tekrarlamayan en uzun ardışık alt string ne kadar uzun? "abcabcbb" için 3 ("abc"), "çiçekçi" için 4 ("içek").

Her karakterin son görüldüğü indeksi bir map'te tutarız. right konumundaki karakter pencerenin içinde daha önce görülmüşse, left doğrudan o eski konumun bir sağına atlar. Map'teki eski konum left'ten gerideyse o karakter artık pencerede değildir ve görmezden alınmalıdır.

package main

import "fmt"

// longestUnique tekrarsız en uzun alt string'in uzunluğunu ve kendisini döndürür.
func longestUnique(s string) (int, string) {
	runes := []rune(s)         // indeksler bayt değil harf olsun
	last := make(map[rune]int) // her harfin son görüldüğü indeks
	best, bestStart, left := 0, 0, 0
	for right, r := range runes {
		if i, ok := last[r]; ok && i >= left {
			left = i + 1 // tekrar eden harfin eski konumunun hemen sağına atla
		}
		last[r] = right
		if right-left+1 > best {
			best, bestStart = right-left+1, left
		}
	}
	return best, string(runes[bestStart : bestStart+best])
}

func main() {
	for _, s := range []string{"abcabcbb", "bbbbb", "pwwkew", "çiçekçi", "abba", ""} {
		n, sub := longestUnique(s)
		fmt.Printf("%-10q → %d %q\n", s, n, sub)
	}
}

"abcabcbb" → 3 "abc"
"bbbbb"    → 1 "b"
"pwwkew"   → 3 "wke"
"çiçekçi"  → 4 "içek"
"abba"     → 2 "ab"
""         → 0 ""

i >= left kontrolünü unutursan "abba" hatalı çıkar: son a geldiğinde map'teki a konumu 0'dır ama pencere zaten 2. indeksten başlıyordur. Kontrol olmadan left 1'e geri gider ve pencere tekrar eden b'leri içerir. Pencere asla geri kaymamalıdır.

Burada m, farklı karakter sayısıdır. Yalnızca ASCII ile çalışıyorsan map yerine [128]int gibi sabit bir dizi daha hızlıdır; Türkçe metin için map[rune]int güvenli seçimdir.

Toplamı hedefe ulaşan en kısa alt dizi

Problem: Pozitif tamsayılardan oluşan bir dizide toplamı en az target olan en kısa ardışık alt dizinin uzunluğu nedir? Yoksa 0 döndür. target = 7, [2, 3, 1, 2, 4, 3] için cevap 2 ([4, 3]).

Bu "en kısa geçerli pencere" varyantıdır:

package main

import (
	"fmt"
	"math"
)

// minSubArrayLen toplamı en az target olan en kısa alt dizinin uzunluğunu döndürür (nums pozitif).
func minSubArrayLen(target int, nums []int) int {
	best := math.MaxInt
	left, sum := 0, 0
	for right, x := range nums {
		sum += x
		for sum >= target {
			best = min(best, right-left+1)
			sum -= nums[left]
			left++
		}
	}
	if best == math.MaxInt {
		return 0
	}
	return best
}

func main() {
	fmt.Println(minSubArrayLen(7, []int{2, 3, 1, 2, 4, 3}))
	fmt.Println(minSubArrayLen(4, []int{1, 4, 4}))
	fmt.Println(minSubArrayLen(11, []int{1, 1, 1, 1, 1}))
}

2
1
0

İçteki for döngüsü seni yanıltmasın. left yalnızca ileri gider ve n'yi geçemez; dolayısıyla iç döngünün tüm çalışmaları boyunca toplam en fazla n kez döner. Dış döngüyle birlikte toplam iş 2n, yani O(n) olur.

Bu çözümün doğru olmasının tek sebebi sayıların pozitif olmasıdır. Pozitif sayılarda pencereyi genişletmek toplamı artırır, daraltmak azaltır. Böylece "toplam hedefe ulaştı, artık bu left için daha uzun pencerelere bakmaya gerek yok" diyebiliriz.

Önek toplamları (prefix sums)

Önek toplamı dizisinde prefix[i], ilk i elemanın toplamıdır. Uzunluğu n + 1'dir ve prefix[0] = 0 olur. Bu küçük hazırlık, herhangi bir aralığın toplamını tek bir çıkarmaya indirir:

indeks:     0   1   2   3   4   5   6   7
nums:       3   1   4   1   5   9   2   6
prefix:  0  3   4   8   9  14  23  25  31
         ↑
      prefix[0] = 0 (boş önek)

nums[2..5] toplamı = prefix[6] - prefix[2] = 23 - 4 = 19   (4 + 1 + 5 + 9)

Genel formül: sum(l..r) = prefix[r+1] - prefix[l]. prefix[r+1] ilk r + 1 elemanı, yani 0..r aralığını içerir; prefix[l] ise 0..l-1 aralığını çıkarır.

Aralık toplamı sorguları

package main

import "fmt"

type PrefixSum struct {
	prefix []int
}

func NewPrefixSum(nums []int) *PrefixSum {
	prefix := make([]int, len(nums)+1)
	for i, x := range nums {
		prefix[i+1] = prefix[i] + x
	}
	return &PrefixSum{prefix: prefix}
}

// Sum, nums[l..r] aralığının (iki uç dahil) toplamını O(1) sürede döndürür.
func (p *PrefixSum) Sum(l, r int) int {
	return p.prefix[r+1] - p.prefix[l]
}

func main() {
	nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
	ps := NewPrefixSum(nums)
	fmt.Println("prefix:", ps.prefix)
	for _, q := range [][2]int{{0, 3}, {2, 5}, {4, 7}, {6, 6}} {
		fmt.Printf("toplam(%d..%d) = %d\n", q[0], q[1], ps.Sum(q[0], q[1]))
	}
}

prefix: [0 3 4 8 9 14 23 25 31]
toplam(0..3) = 9
toplam(2..5) = 19
toplam(4..7) = 22
toplam(6..6) = 2

Hazırlık O(n), her sorgu O(1). q sorgu için toplam O(n + q); her sorguyu döngüyle hesaplasaydın O(n·q) olurdu. Dizi sık sık değişiyorsa önek toplamlarını her güncellemede yeniden kurmak gerekir; o durumda Fenwick veya segment ağacı kullanılır.

Toplamı k olan alt dizi sayısı

Problem: Negatif sayılar da içerebilen bir dizide toplamı tam k olan kaç ardışık alt dizi var? [3, 4, 7, 2, -3, 1, 4, 2] ve k = 7 için cevap 4: [3, 4], [7], [7, 2, -3, 1], [1, 4, 2].

Anahtar gözlem: l..r aralığının toplamı prefix[r+1] - prefix[l]'dir. Bu toplamın k olması, prefix[l] = prefix[r+1] - k demektir. O hâlde diziyi soldan gezerken şimdiye kadar gördüğümüz önek toplamlarını bir map'te sayarsak, her konumda "kaç tane önceki önek, şu anki toplam eksi k'ya eşit?" sorusunun cevabı, o konumda biten geçerli alt dizi sayısını verir.

0:1 başlangıç kaydı "boş önek"i temsil eder ve dizinin başından başlayan alt dizileri ([3, 4] gibi) saymamızı sağlar.

package main

import "fmt"

// subarraySum toplamı tam k olan alt dizileri önek toplamı ve map ile sayar.
func subarraySum(nums []int, k int) int {
	seen := map[int]int{0: 1} // boş önek: toplam 0, bir kez
	sum, count := 0, 0
	for _, x := range nums {
		sum += x
		count += seen[sum-k] // bu konumda biten ve toplamı k olan alt diziler
		seen[sum]++
	}
	return count
}

// windowCount aynı soruyu kayan pencereyle çözmeye çalışır; yalnızca pozitif sayılarda doğrudur.
func windowCount(nums []int, k int) int {
	left, sum, count := 0, 0, 0
	for right, x := range nums {
		sum += x
		for sum > k && left <= right {
			sum -= nums[left]
			left++
		}
		if sum == k {
			count++
		}
	}
	return count
}

func main() {
	nums := []int{3, 4, 7, 2, -3, 1, 4, 2}
	fmt.Println("önek + map:    ", subarraySum(nums, 7))
	fmt.Println("kayan pencere: ", windowCount(nums, 7))

	positive := []int{1, 2, 3, 4, 2, 1, 3}
	fmt.Println("pozitif dizide:", subarraySum(positive, 6), windowCount(positive, 6))
}

önek + map:     4
kayan pencere:  2
pozitif dizide: 3 3

Kayan pencere neden negatiflerde çöküyor? Pencere yaklaşımı "toplam k'yı geçtiyse soldan çıkar" kuralına dayanır. Bu kural, sağa yeni eleman eklemenin toplamı asla azaltmadığı varsayımıyla güvenlidir. Negatif sayılar bu varsayımı yıkar: [7, 2] penceresi 9'a çıkıp daraltıldığında, birkaç adım sonra gelen -3 toplamı yeniden 7'ye indirebilecekken sol uç çoktan ilerlemiş olur. Nitekim çıktıda kayan pencere [7, 2, -3, 1] ve [1, 4, 2] alt dizilerini kaçırıp 2 buluyor. Önek toplamı yöntemi ise hiçbir karar vermez, her bitiş noktası için olası tüm başlangıçları map sayesinde tek adımda sayar; bu yüzden işaretten bağımsız olarak doğrudur.

İki boyutlu önek toplamları

Aynı fikir matrislere de genişler. P[i][j], sol üst köşesi (0, 0), sağ alt köşesi (i-1, j-1) olan dikdörtgenin toplamı olsun. Hesaplarken ve sorgularken dahil etme-dışlama ilkesini kullanırız:

P[i+1][j+1] = M[i][j] + P[i][j+1] + P[i+1][j] − P[i][j]

   ┌─────────┬───┐        yukarıdaki blok  P[i][j+1]
   │    A    │ B │        soldaki blok     P[i+1][j]
   ├─────────┼───┤        A iki kez sayıldı → bir kez çıkar: P[i][j]
   │    C    │ x │        x = M[i][j]
   └─────────┴───┘

Sorgu (r1, c1) .. (r2, c2):
toplam = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]

package main

import "fmt"

type Matrix2D struct {
	p [][]int
}

func NewMatrix2D(m [][]int) *Matrix2D {
	rows, cols := len(m), len(m[0])
	p := make([][]int, rows+1)
	for i := range p {
		p[i] = make([]int, cols+1)
	}
	for i := range rows {
		for j := range cols {
			p[i+1][j+1] = m[i][j] + p[i][j+1] + p[i+1][j] - p[i][j]
		}
	}
	return &Matrix2D{p: p}
}

// Sum, (r1, c1) sol üst ve (r2, c2) sağ alt köşeli dikdörtgenin toplamını O(1) sürede döndürür.
func (m *Matrix2D) Sum(r1, c1, r2, c2 int) int {
	p := m.p
	return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]
}

func main() {
	grid := [][]int{
		{3, 0, 1, 4},
		{5, 6, 3, 2},
		{1, 2, 0, 1},
		{4, 1, 0, 1},
	}
	m := NewMatrix2D(grid)
	fmt.Println("satır 1-2, sütun 1-3:", m.Sum(1, 1, 2, 3))
	fmt.Println("tüm matris:          ", m.Sum(0, 0, 3, 3))
	fmt.Println("satır 2-3, sütun 0-1:", m.Sum(2, 0, 3, 1))
}

satır 1-2, sütun 1-3: 14
tüm matris:           34
satır 2-3, sütun 0-1: 8

Hazırlık O(R·C), her dikdörtgen sorgusu O(1). Görüntü işlemede bulanıklaştırma filtreleri ve bir haritadaki bölge istatistikleri bu tekniğin tipik kullanım alanlarıdır.

Fark dizileri

Önek toplamının tersini düşün. Bu kez sorgular değil güncellemeler çok: "2. ile 5. günler arasındaki bütün değerlere 3 ekle" gibi yüzlerce işlem yapılıyor, en sonda da dizinin son hâli okunuyor. Her güncellemeyi döngüyle uygulamak O(n) sürer, q güncelleme için O(n·q).

Fark dizisinde diff[i] = a[i] - a[i-1] tutulur. l..r aralığına v eklemek, farklar dizisinde yalnızca iki hücreyi değiştirir: diff[l] += v (aralığın başında değer v kadar zıplar) ve diff[r+1] -= v (aralığın bittiği yerde geri iner). Bütün güncellemelerden sonra diff üzerinde önek toplamı almak diziyi geri kurar.

Örnek: Bir otelin 7 günlük doluluğunu hesaplayalım. Rezervasyonlar: 1–3. günler 2 oda, 2–5. günler 3 oda, 0–1. günler 1 oda.

gün:              0   1   2   3   4   5   6   (7)
(1..3, +2):           +2          −2
(2..5, +3):               +3              −3
(0..1, +1):      +1      −1
diff:             1   2   2   0  −2   0  −3    0

önek toplamı:     1   3   5   5   3   3   0     ← her günkü dolu oda sayısı

package main

import "fmt"

type Booking struct {
	From, To int // iki uç dahil gün aralığı
	Rooms    int
}

// occupancy, her rezervasyonu O(1) sürede işleyip günlük dolu oda sayılarını döndürür.
func occupancy(days int, bookings []Booking) []int {
	diff := make([]int, days+1) // To+1 için bir hücre fazladan
	for _, b := range bookings {
		diff[b.From] += b.Rooms
		diff[b.To+1] -= b.Rooms
	}
	fmt.Println("diff:  ", diff)

	result := make([]int, days)
	running := 0
	for d := range days {
		running += diff[d]
		result[d] = running
	}
	return result
}

func main() {
	bookings := []Booking{
		{From: 1, To: 3, Rooms: 2},
		{From: 2, To: 5, Rooms: 3},
		{From: 0, To: 1, Rooms: 1},
	}
	fmt.Println("doluluk:", occupancy(7, bookings))
}

diff:   [1 2 2 0 -2 0 -3 0]
doluluk: [1 3 5 5 3 3 0]

q güncelleme ve tek bir okuma için toplam maliyet O(n + q). Aynı teknik iki boyuta da taşınabilir: bir dikdörtgene değer eklemek için dört köşeye +v, -v, -v, +v yazılır ve sonunda 2B önek toplamı alınır. Güncellemeler ile okumalar sürekli iç içe geçiyorsa fark dizisi yetmez; yine segment ağacına ihtiyaç duyarsın.

Desen tanıma ipuçları

Bu desenlerin gücü, problemi okurken doğru sinyali yakalamaktan gelir. Aşağıdaki tablo, sık görülen ifadeleri akla gelmesi gereken tekniklerle eşleştiriyor:

Genel strateji olarak önce kaba kuvvet çözümünü yaz ve iç döngünün tekrar tekrar hesapladığı şeye bak. Aynı toplamı yeniden hesaplıyorsa önek toplamı ya da kayan pencere; eleneceği belli olan çiftleri deniyorsa iki işaretçi aradığın şeydir. Daha fazla strateji için problem çözme dersine göz at.

Sık yapılan hatalar

• Sıralı olmayan dizide karşılıklı uç kullanmak: Çift toplamı için iki işaretçi, sıralamanın verdiği "sağdaki büyüktür" bilgisine dayanır. Dizi sıralı değilse önce sırala ya da hash map kullan.
• String'lerde bayt indeksiyle çalışmak: s[i] ve len(s) bayt düzeyindedir. Türkçe metinde palindrom kontrolü veya tekrarsız alt string için []rune kullan; büyük/küçük harf için unicode.TurkishCase'i unut.
• 3Sum'da tekrarları atlamamak: Sonuç listesi aynı üçlüyle dolar. Hem i için hem de bulunan her üçlüden sonra left ve right için eşit değerleri geç.
• Kayan pencerede sol ucu geri götürmek: left = last[r] + 1 ataması, eski konum pencerenin dışındaysa left'i geriye çeker. i >= left kontrolü veya left = max(left, last[r]+1) kullan.
• Negatif sayılarda değişken pencere kullanmak: Genişletmenin toplamı artırdığı varsayımı çöker; önek toplamı ve hash map'e geç.
• Önek dizisinde bir kaydırma hatası: prefix uzunluğunu n yapıp prefix[r] - prefix[l-1] yazmak l = 0 için panik üretir. n + 1 uzunluk ve prefix[r+1] - prefix[l] formülü bu durumu kendiliğinden çözer.
• Map'e boş öneki eklemeyi unutmak: seen[0] = 1 olmadan dizinin başından başlayan alt diziler sayılmaz.
• Go'da negatif mod: -3 % 5 Go'da -3 olur, 2 değil. Mod tabanlı önek problemlerinde ((x % k) + k) % k ile normalleştir.
• Fark dizisini n uzunlukta ayırmak: diff[r+1] son eleman için taşar; bir hücre fazladan ayır.

Alıştırmalar

package main

import "fmt"

func sortedSquares(nums []int) []int {
	result := make([]int, len(nums))
	left, right := 0, len(nums)-1
	for pos := len(nums) - 1; pos >= 0; pos-- {
		l, r := nums[left]*nums[left], nums[right]*nums[right]
		if l > r {
			result[pos] = l
			left++
		} else {
			result[pos] = r
			right--
		}
	}
	return result
}

func main() {
	fmt.Println(sortedSquares([]int{-4, -1, 0, 3, 10}))
	fmt.Println(sortedSquares([]int{-7, -3, 2, 3, 11}))
	fmt.Println(sortedSquares([]int{-5, -3, -1}))
}

[0 1 9 16 100]
[4 9 9 49 121]
[1 9 25]

package main

import "fmt"

func checkInclusion(pattern, text string) bool {
	p, t := []rune(pattern), []rune(text)
	if len(p) > len(t) {
		return false
	}
	diff := make(map[rune]int) // desendeki adet - penceredeki adet
	for _, r := range p {
		diff[r]++
	}
	mismatched := len(diff) // farkı sıfır olmayan harf sayısı

	update := func(r rune, delta int) {
		before := diff[r]
		diff[r] += delta
		switch {
		case before == 0:
			mismatched++ // sıfırdan çıktı
		case diff[r] == 0:
			mismatched-- // sıfıra indi
		}
	}

	for i, r := range t {
		update(r, -1) // r pencereye girdi
		if i >= len(p) {
			update(t[i-len(p)], +1) // en soldaki harf pencereden çıktı
		}
		if mismatched == 0 {
			return true
		}
	}
	return false
}

func main() {
	fmt.Println(checkInclusion("ab", "eidbaooo"))
	fmt.Println(checkInclusion("ab", "eidboaoo"))
	fmt.Println(checkInclusion("çay", "kayçak"))
	fmt.Println(checkInclusion("ışık", "kışıkaç"))
}

true
false
true
true

package main

import "fmt"

func subarraysDivByK(nums []int, k int) int {
	remainders := make([]int, k) // remainders[r]: kalanı r olan önek sayısı
	remainders[0] = 1            // boş önek
	sum, count := 0, 0
	for _, x := range nums {
		sum += x
		r := ((sum % k) + k) % k // Go'da -2 % 5 == -2; [0, k) aralığına taşı
		count += remainders[r]
		remainders[r]++
	}
	return count
}

func main() {
	fmt.Println(subarraysDivByK([]int{4, 5, 0, -2, -3, 1}, 5))
	fmt.Println(subarraysDivByK([]int{5}, 9))
	fmt.Println(subarraysDivByK([]int{-1, 2, 9}, 2))
}

7
0
2

package main

import "fmt"

func minWindow(s, t string) string {
	src, pat := []rune(s), []rune(t)
	need := make(map[rune]int)
	for _, r := range pat {
		need[r]++
	}
	missing := len(pat) // pencerede henüz bulunmayan harf adedi
	bestLen, bestStart := len(src)+1, 0
	left := 0
	for right, r := range src {
		if need[r] > 0 {
			missing--
		}
		need[r]-- // negatif değer: bu harften fazlası var

		for missing == 0 {
			if right-left+1 < bestLen {
				bestLen, bestStart = right-left+1, left
			}
			out := src[left]
			need[out]++
			if need[out] > 0 {
				missing++ // gerekli bir harfi kaybettik
			}
			left++
		}
	}
	if bestLen > len(src) {
		return ""
	}
	return string(src[bestStart : bestStart+bestLen])
}

func main() {
	fmt.Printf("%q\n", minWindow("ADOBECODEBANC", "ABC"))
	fmt.Printf("%q\n", minWindow("a", "aa"))
	fmt.Printf("%q\n", minWindow("kırmızı kazak", "ıkz"))
}

"BANC"
""
"zı k"

Kısa sınav

Özet

• Karşılıklı uçlardan iki işaretçi, sıralı dizilerde her adımda bir satırı ya da sütunu eleyerek çift toplamı, kap problemi ve palindrom kontrolünü O(n)'de çözer; 3Sum ise sıralama ve bir dış döngüyle O(n²) olur.
• Hızlı ve yavaş işaretçi, okuma ile yazmayı ayırarak dilimleri yerinde filtreler (slices.Compact bu fikirle çalışır); bağlı listelerde Floyd'un döngü tespitinin temelidir.
• Sabit pencerede her kaymada yalnızca giren ve çıkan eleman işlenir; O(n·k) iş O(n)'e iner.
• Değişken pencerede sağ uç genişletir, sol uç geçerliliği geri kazanana kadar daraltır. Her eleman bir kez girip bir kez çıktığı için iç içe döngüye rağmen O(n) sürer; ama koşulun monoton olması şarttır.
• Türkçe metinlerde indeksleri rune üzerinden tut ve büyük/küçük harf için unicode.TurkishCase kullan.
• Önek toplamları aralık toplamını prefix[r+1] - prefix[l] çıkarmasına indirir. Hash map ile birleşince negatif sayılar içeren "toplamı k olan alt dizi" problemlerini O(n)'de çözer; 2B sürümü dahil etme-dışlama kullanır.
• Fark dizileri çok sayıda aralık güncellemesini hücre başına iki işleme indirir; sonda alınan tek bir önek toplamı diziyi geri kurar.
• Sinyal ile teknik arasındaki bağı kur: sıralı + çift → iki işaretçi, ardışık + monoton koşul → pencere, negatifler + toplam sayma → önek toplamı ve map.