❓ Как найти два числа с заданной суммой за O(n)

Наивное решение это два вложенных цикла и O(n²). Оптимальное использует map. Для каждого элемента вычисляем complement = target - s[i] и смотрим, есть ли он уже в map. Если есть, нашли пару. Если нет, кладём текущий элемент в map и идём дальше.

func twoSum(nums []int, target int) (int, int) {
    seen := make(map[int]int) // значение -> индекс
    for i, v := range nums {
        if j, ok := seen[target-v]; ok {
            return j, i
        }
        seen[v] = i
    }
    return -1, -1
}

Сначала ищем complement в map, только потом добавляем текущий элемент. Это защищает от ложного совпадения с самим собой при target = 2 * v.

🐸 Библиотека Go для собеса