الگوریتم در گولنگ (قسمت اول): Two Sum و برخورد سخت با دیوار Tech Lead!

قصد داریم در یک مجموعه مقاله، نحوه حل و بررسی یک سری از الگوریتم‌ها را با هم شخم بزنیم که قاعدتاً از سطح پایین شروع شده و به بالاترین سطح خواهد رسید.

الگوریتم اولی که مورد بحث قرار می‌دهیم، پای ثابت مصاحبه‌ها یعنی Two Sum است.

صورت سوال

Two Sum

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target.

Input: nums = [2, 7, 11, 15], target = 9

Output: [0, 1] // nums[0] + nums[1] = 2 + 7 = 9

Input: nums = [3, 2, 4], target = 6

Output: [1, 2]

Input: nums = [3, 3], target = 6

Output: [0, 1]

Constraints:

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists

درک مسئله: ذهن انسان در برابر ماشین

در بحث چالش‌های برنامه‌نویسی، فهمیدن صورت سوال از خود کد زدن مهم‌تر است؛ مخصوصاً وقتی در یک مصاحبه فنی لایو هستید و قلب‌تان در دهان‌تان می‌تپد!

بیایید بی‌درنگ برویم سراغ مسئله. ما باید مجموع دو عدد را پیدا کنیم. اگر به عنوان یک انسان به آرایه [2, 7, 11, 15] و هدف 999 نگاه کنیم، در کسری از ثانیه چشم‌مان عدد ۲ و ۷ را اسکن می‌کند و می‌گوییم “یافتم!”. اما همان‌طور که می‌دانید، ماشین‌ها مثل ما بینایی محیطی ندارند. کامپیوتر کورِ بیچاره نمی‌تواند همه اعداد را با هم ببیند.

پس ذهن ما به صورت پیش‌فرض می‌رود سراغ پیمایش یکی‌یکی عناصر: اول ۱۵ را برمی‌داریم، با ۱۱ جمع می‌کنیم، می‌شود ۲۶ (هدف ما نیست). بعد می‌رویم سراغ بعدی و الی آخر…

اگر بخواهیم همین منطق خام را تبدیل به کد گولنگ کنیم، به چیزی شبیه به این می‌رسیم:

package main

import "fmt"

func twoSum(nums []int, target int) []int {
	// Base check
	if len(nums) < 2 {
		return nil
	}
	
	result := []int{}
	// Iterate through each element
	for i := 0; i < len(nums); i++ {
		// Compare with all subsequent elements
		for j := i + 1; j < len(nums); j++ {
			if nums[i]+nums[j] == target {
				result = append(result, i, j)
				return result
			}
		}
	}
	return result
}

func main() {
	arr := []int{2, 7, 11, 15}
	res := twoSum(arr, 9)
	fmt.Println(res)
}

کالبدشکافی کد بالا:

در این کد ما از دو حلقه for تودرتو استفاده کرده‌ایم. حلقه اول با ایندکس i روی تک‌تک عناصر آرایه حرکت می‌کند. در همان حال، حلقه دوم با ایندکس j از خانه بعدی (i + 1) شروع به حرکت می‌کند تا عدد فعلی را با تمام اعداد جلویی خودش جمع کند. در خط if nums[i]+nums[j] == target چک می‌کنیم که آیا مجموع این دو عدد با هدف برابر است یا خیر. اگر برابر بود، مستقیماً یک اسلایس (Slice) شامل هر دو ایندکس []int{i, j} را بر میگرداند

کد کار کرد! اما… (ورود Tech Lead )

شما با خوشحالی کد را می‌زنید، ران می‌کنید، خروجی درست است (Happy Path را پاس می‌کند) و لبخند رضایت بر لبان‌تان می‌نشیند. کد را برای Code Review می‌فرستید. اما اگر مرورگر کد شما یک Tech Lead سخت‌گیر (مثلاً در گوگل) باشد، کد را با یک کامنت تند و تیز به شما برمی‌گرداند.

بیایید ببینیم این کد چه ایراداتی دارد و چرا در یک مصاحبه واقعی رد می‌شود:

۱. فاجعه پیچیدگی زمانی (Wrong Complexity):

استفاده از حلقه تودرتو (Nested Loop) یعنی شما دارید زمان را می‌کشید! پیچیدگی زمانی این کد O(n2) است. شاید برای ۴ تا عدد جواب بدهد، اما اگر طول آرایه ما ۱۰ به توان ۴ باشد (طبق محدودیت‌ها)، این کد به نفس‌نفس می‌افتد. ما یک راه‌حل O(n) نیاز داریم.

۲. منطق اعتبارسنجی روی هواست!

گاهی اوقات بچه‌ها برای محکم‌کاری میان شرط‌هایی مثل target >= 10000 می‌نویسند تا جلوی خطای ورودی را بگیرند. اما دقت کنید! محدودیت طول آرایه ۱۰ به توان ۴ است، در حالی که عدد target می‌تواند تا ۱۰ به توان ۹ باشد . قاطی کردن این محدودیت‌ها با هم نشان می‌دهد صورت سوال را دقیق نخوانده‌اید.

۳. چاپ کردن داخل یک تابع منطقی؟ هرگز!

هیچ‌وقت داخل تابعی که قرار است یک ابزار (Library Function) باشد، از fmt.Println استفاده نکنید. تابع شما فقط باید دیتا (یا Error) برگرداند. این وظیفه فراخواننده (Caller) است که تصمیم بگیرد دیتا را چاپ کند، در دیتابیس ذخیره کند یا به API بفرستد.

۴. ساختن کلیدهای استرینگ در حلقه‌های داغ (Performance Killer):

برخی برای فرار از حلقه تودرتو، سعی می‌کنند ترکیب اعداد را به صورت یک رشته (String) مثل "a,b" در یک Map ذخیره کنند تا تکراری‌ها را هندل کنند. استفاده از توابعی مثل strconv.Itoa داخل یک حلقه که هزاران بار می‌چرخد، باعث تخصیص حافظه (Memory Allocation) شدید شده و در بررسی‌های پرفورمنس شما را نابود می‌کند.

یه چیزی شبیه این :)

package main

import (
	"fmt"
	"strconv"
)

// Bad practice: Using strings and strconv for caching inside a loop
func twoSumStrconv(nums []int, target int) []int {
	seenPairs := make(map[string]bool)

	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			a, b := nums[i], nums[j]
			
			// Order them to create a unique key
			if a > b {
				a, b = b, a
			}
			
			// Creating strings in a hot loop -> High memory allocation!
			key := strconv.Itoa(a) + "," + strconv.Itoa(b)
			
			if !seenPairs[key] && nums[i]+nums[j] == target {
				return []int{i, j}
			}
			seenPairs[key] = true
		}
	}
	return nil
}

استفاده از توابعی مثل strconv.Itoa و جمع کردن رشته‌ها (+) داخل حلقه‌ای که هزاران بار می‌چرخد، باعث تخصیص حافظه (Memory Allocation) شدید شده و در بررسی‌های پرفورمنس شما را نابود می‌کند. ضمن اینکه این کد هنوز درگیر حلقه تودرتو و پیچیدگی O(n2)O(n^2)O(n2) است!

تغییر زاویه دید: ترفند طلایی

تک‌لید به شما می‌گوید: «به جای اینکه بگردی ببینی فلان عدد با چی جمع بشه می‌شه هدف، از خودت بپرس: من برای رسیدن به هدف چی کم دارم؟ و آیا قبلاً اون چیزی که کم دارم رو دیدم؟»

اینجاست که ساختار داده HashMap (در گولنگ همان map) مثل یک قهرمان وارد می‌شود.

فرض کنید target = 9 است:

1. عدد اول ۲ است. می‌پرسیم: “برای رسیدن به ۹ چی کم دارم؟” جواب: ۷. آیا قبلاً ۷ را دیده‌ام؟ نه. پس خود ۲ و ایندکس آن را در دفترچه‌ام (Map) یادداشت می‌کنم.

2. عدد بعدی ۷ است. می‌پرسیم: “برای رسیدن به ۹ چی کم دارم؟” جواب: ۲. آیا قبلاً ۲ را دیده‌ام؟ بله! در دفترچه‌ام هست. تمام شد! ما جواب را در یک دور گشتن (Single Pass) پیدا کردیم.

راه‌حل بهینه و حرفه‌ای (The Optimal Solution)

با این دیدگاه، کدمان را به شکلی می‌نویسیم که پیچیدگی زمانی آن O(n) و پیچیدگی فضایی آن (به خاطر استفاده از مپ) O(n) باشد. در این حالت، جستجو در مپ زمانش O(1) است.

func twoSum(nums []int, target int) []int {
	// Create a map to store numbers we have seen so far
	// Key: the number itself, Value: its index in the array
	seen := make(map[int]int)

	for i, num := range nums {
		// What do we need to reach the target?
		complement := target - num
		
		// Have we seen this complement before? (O(1) lookup)
		if index, ok := seen[complement]; ok {
			// If yes, return its index and the current index
			return []int{index, i}
		}
		
		// If not, record the current number and its index in our map
		seen[num] = i
	}
	
	// Return nil if no solution is found (though constraints say one exists)
	return nil 
}

توضیح خط به خط:

seen := make(map[int]int):

در گولنگ، map همان ساختار داده معروف Hash Table (یا Dictionary در پایتون) است. ما در اینجا یک دفترچه یادداشت به نام seen (به معنی “دیده‌شده‌ها”) می‌سازیم.

• کلید (Key) مپ: خودِ عدد را ذخیره می‌کند (نوع int).

• مقدار (Value) مپ: ایندکسِ (موقعیت) آن عدد در آرایه را ذخیره می‌کند (نوع int).

• for i, num := range nums:

یک حلقه که روی آرایه nums حرکت می‌کند. در هر چرخش، i شماره خانه (ایندکس) و num خودِ عدد را به ما می‌دهد. ما فقط یک بار روی آرایه حرکت می‌کنیم (Single Pass).

complement := target - num:

این قلب تپنده‌ی منطق ماست. complement یعنی “مکمل” یا “متمم”. ما از خودمان می‌پرسیم: «حالا که عدد فعلی من num است، برای رسیدن به target چه عددی کم دارم؟»

مثال: اگر هدف ما 999 باشد و عدد فعلی ما 222، متمم می‌شود 9−2=79 - 2 = 79−2=7.

if index, ok := seen[complement]; ok:

حالا می‌رویم سراغ دفترچه یادداشتمان (seen). می‌گوییم: «آیا عدد متمم (مثلاً 7) قبلاً در دفترچه من ثبت شده است؟»

در گولنگ، وقتی کلیدی را از یک مپ می‌خوانید، دو خروجی به شما می‌دهد: اولی مقدار آن کلید (index) و دومی یک متغیر بولین (ok) که می‌گوید آیا اصلاً این کلید وجود داشت یا نه.

جستجو در مپ بسیار سریع است و پیچیدگی زمانی آن O(1) می‌باشد.

return []int{index, i}:

اگر متغیر ok برابر true بود (یعنی متمم را قبلاً دیده‌ایم)، تبریک می‌گویم! شما جواب را پیدا کردید. ما بلافاصله یک آرایه شامل ایندکسِ عدد قبلی (index) و ایندکسِ عدد فعلی (i) را برمی‌گردانیم.

seen[num] = i:

اگر به جواب نرسیدیم (یعنی ok برابر false بود)، عدد فعلی (num) را به عنوان کلید و ایندکس آن (i) را به عنوان مقدار در دفترچه یادداشت می‌کنیم تا شاید در چرخه‌های بعدی، متممِ یک عدد دیگر باشد.

تست کیس‌ها (Edge Cases) و اثبات کد

برای اینکه نشان دهیم کد ما چقدر قدرتمند است، باید آن را با تست‌کیس‌های مختلف (اعداد منفی، صفر، تکراری‌ها و…) بسنجیم. در گولنگ بهترین راه استفاده از Table-Driven Tests است.

کد زیر را می‌توانید در فایلی مثل twosum_test.go قرار دهید تا تمام لبه‌های تاریک (Edge Cases) را تست کند:

package main

import (
	"reflect"
	"testing"
)

func TestTwoSum(t *testing.T) {
	// Table-driven tests covering various edge cases
	tests := []struct {
		name     string
		nums     []int
		target   int
		expected []int
	}{
		{
			name:     "Happy Path - Simple positive numbers",
			nums:     []int{2, 7, 11, 15},
			target:   9,
			expected: []int{0, 1},
		},
		{
			name:     "Edge Case - Negative numbers",
			nums:     []int{-3, 4, 3, 90},
			target:   0,
			expected: []int{0, 2},
		},
		{
			name:     "Edge Case - Duplicate numbers",
			nums:     []int{3, 3},
			target:   6,
			expected: []int{0, 1},
		},
		{
			name:     "Edge Case - Zero target with negatives",
			nums:     []int{-5, 0, 5},
			target:   0,
			expected: []int{0, 2},
		},
		{
			name:     "Edge Case - Large Target (Constraint testing)",
			nums:     []int{1000000000, 2, 4, 500000000}, // 10^9 and 5*10^8
			target:   1500000000,
			expected: []int{0, 3},
		},
	}

	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			result := twoSum(tt.nums, tt.target)
			// reflect.DeepEqual is great for comparing slices
			if !reflect.DeepEqual(result, tt.expected) {
				t.Errorf("got %v, want %v", result, tt.expected)
			}
		})
	}
}

جمع‌بندی نکات این الگوریتم:

• پیمایش تک‌مرحله‌ای (Single Pass): نیازی نیست همه چیز را چند بار حساب کنید. با استفاده از حافظه اضافی (Map)، زمان را می‌خریم.

• جلوگیری از محاسبات تکراری: ما فقط به گذشته نگاه می‌کنیم (seen). این باعث می‌شود یک عنصر را با خودش جمع نکنیم (چون در حلقه تودرتو اگر حواستان نباشد ممکن است ایندکس i را با خودش جمع کنید).

• سرعت جستجو: خاصیت اصلی Hashmap ها پیدا کردن مقادیر در زمان O(1) است که کلید فرار ما از کابوس O(n2) بود.

در مقالات بعدی سراغ چالش‌های خفن‌تری می‌رویم که ذهن‌تان را حسابی قلقلک بدهد!