> Реализовать функцию проверки наличия двух разных чисел в слайсе с заданной суммой без повторного использования числа (Go)

Короткий ответ

Классическая задача two-sum на слайсе. Для отсортированного слайса применяем два указателя за O(n) без дополнительной памяти. Для неотсортированного используем map для хранения уже встреченных значений за O(n) времени и O(n) памяти. Числа должны быть разными индексами, но значения могут совпадать, если это разные элементы.

Подход к решению

Для неотсортированного слайса идём одним проходом, поддерживая map[value]index уже просмотренных элементов. На каждом шаге проверяем, есть ли в map значение target - nums[i]. Если есть и его индекс отличается от текущего, возвращаем true. Это даёт O(n) по времени и O(n) по памяти. Для отсортированного слайса оптимальнее два указателя: left и right двигаются навстречу, сравнивая сумму с target. Такой подход даёт O(n) времени и O(1) памяти. Выбор зависит от контракта функции: сортировка на месте мутирует входной слайс, что не всегда допустимо. В Go слайсы передаются по значению заголовка, но базовый массив общий, поэтому сортировка затронет вызывающего.

Пример кода

GO
package twosum

// HasPairWithSum возвращает true, если в nums есть два разных индекса
// с суммой target. Работает за O(n) времени и O(n) памяти.
func HasPairWithSum(nums []int, target int) bool {
    seen := make(map[int]int, len(nums))
    for i, v := range nums {
        need := target - v
        if j, ok := seen[need]; ok && j != i {
            return true
        }
        seen[v] = i
    }
    return false
}

// HasPairWithSumSorted работает за O(n) времени и O(1) памяти,
// но требует отсортированный по возрастанию слайс.
func HasPairWithSumSorted(nums []int, target int) bool {
    left, right := 0, len(nums)-1
    for left < right {
        sum := nums[left] + nums[right]
        switch {
        case sum == target:
            return true
        case sum < target:
            left++
        default:
            right--
        }
    }
    return false
}

Edge cases

Слайс длиной меньше двух возвращает false. Дубликаты значений допустимы, если это разные индексы: например, nums = [3, 3], target = 6 даёт true. Один и тот же элемент нельзя использовать дважды: nums = [3], target = 6 даёт false. Отрицательные числа и ноль обрабатываются корректно, так как map и арифметика не зависят от знака. Переполнение int при сложении больших значений может дать неверный результат в варианте с двумя указателями, если сумма выходит за границы типа. Для отсортированного варианта важно, чтобы слайс был действительно отсортирован, иначе алгоритм вернёт неверный ответ.

Как отвечать на собеседовании

Сначала уточните у интервьюера: отсортирован ли слайс, можно ли мутировать вход, допустимы ли дубликаты, какой тип чисел. Затем предложите два подхода и обоснуйте trade-off между памятью и требованием к сортировке. Напишите код с явной обработкой условия j != i, чтобы исключить повторное использование одного элемента. Проговорите сложность вслух. Если интервьюер просит оптимизировать память, переходите к двум указателям с предварительной сортировкой, отметив, что сортировка даёт O(n log n).

Что проверяет интервьюер

Понимание классической задачи two-sum и её вариантов. Умение выбирать структуру данных под ограничения по памяти и времени. Внимание к деталям: разные индексы, дубликаты, переполнение, мутация входного слайса. Навык обсуждать trade-off и уточнять требования до написания кода. Аккуратность в Go: работа с map, слайсами и граничными условиями цикла.