Задача «Сумма двух» - разбор алгоритмической задачи

Задача «Сумма двух» (Two Sum) — это классическая алгоритмическая задача, которая обычно формулируется так:

список чисел, найти порядковые номера (индексы) двух чисел из этого списка, которые в сумме дают заданное число-цель (target)

Например, для чисел:

2, 3, 7, 11, 15}

и целевого числа 9
ответ будет:

2 и 7

Оптимальное решение

Цель задачи - получить сложность O(N), относительно чтения массивы, т.е. линейную сложность

Главная идея:

1. использовать хэш-мэп, чтобы хранить уже пройденные числа как ключи, а их индексы - как значения
2. и искать в этом хэш-мэпе для очередного числа пару, получив значение для поиска как разность целевого числа (которое target) и текущего.

Возможная реализация (golang)

Рассмотрим код на golang:

package main

import "fmt"

func twoSum(nums []int, target int) []int {
	seen := make(map[int]int) // инициаллизиуем хэш-таблицу

	for i, value := range nums {
		needed := target - value
		if index, exists := seen[needed]; exists {
			return []int{index, i}
		}
		seen[value] = i
	}
	return []int{}
}

func main() {
	nums := []int{2, 3, 7, 11, 15}
	target := 9

	result := twoSum(nums, target)
	if len(result) == 2 {
		fmt.Printf("Индексы: %v (числа: %d + %d = %d)\n",
			result, nums[result[0]], nums[result[1]], target)
	} else {
		fmt.Println("Пара не найдена")
	}
}