Two Sum

Q: Какова временная сложность задачи Two Sum?

Решение с хеш-таблицей работает за время O(n) , поскольку оно проходит по каждому числу один раз, а каждая операция поиска или вставки в среднем занимает постоянное время. Для хеш-таблицы требуется дополнительное пространство O(n) . Проверка каждой пары занимает время O(n²) и пространство O(1) .

ЛегкоХеширование

+10

Дан массив целых чисел nums и целое число target. Ровно два элемента массива nums, находящиеся на разных позициях, в сумме дают target. Верните индексы этих двух элементов, сначала меньший индекс.

Функция

twoSum(nums: integer-array, target: integer) → integer-array

numsinteger-array: массив целых чисел для поиска
targetinteger: сумма двух элементов должна достигать
Возвращаетinteger-array: два индекса, сначала меньший

Ограничения

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
-10⁹ ≤ target ≤ 10⁹
Ровно одна пара различных позиций в сумме дает target.

Примеры

Ввод: nums = [3, 8, 12, 5]target = 17
Вывод: [2, 3]
Пояснение: 12 находится по индексу 2, а 5 — по индексу 3, и 12 + 5 = 17. Ни одна другая пара не дает в сумме 17.

Дополнительный вопрос

Если nums уже отсортирован, сможете ли вы найти пару за время O(n), используя только O(1) дополнительной памяти?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Проверка каждой пары работает, но объём работы растёт пропорционально квадрату длины. Переверни вопрос: остановившись на числе x, ты уже знаешь, что его парой должно быть target - x. Хеш-таблица за константное время сообщает, встречалось ли тебе уже это значение, поэтому достаточно одного прохода.

Проверьте каждую пару

Верно, но не успевает на самых больших тестах

Идея

Зафиксируй первый индекс i и перебирай каждый индекс j справа от него, пока nums[i] + nums[j] не станет равным target. Если начать j с i + 1, позиция не будет сопоставляться сама с собой, каждая пара будет проверена один раз, а меньший индекс будет первым. Нужная тебе пара — одна из проверяемых, поэтому ты её найдёшь.

n чисел образуют около n²/2 пар: n = 10^4 означает почти 5 × 10^7 сложений.

Алгоритм

Перебирай i по всем индексам nums.
Для каждого i перебирай j от i + 1 до последнего индекса.
Если nums[i] + nums[j] равно target, верни [i, j].
Если оба цикла завершатся, верни пустой массив. В условии обещано, что этого никогда не произойдёт.

def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        # Only look at partners to the right, so each pair is checked once.
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Один проход с хеш-таблицей

Идея

Для фиксированного nums[i] внутренний цикл перебора ищет значение, которое заранее известно: target - nums[i]. Этот поиск по сути является поиском по таблице, а хеш-таблица, сопоставляющая значения индексам, выполняет поиск за постоянное время в среднем.

Сначала ищи, потом сохраняй. Тогда число может составить пару только с числом, которое встретилось раньше, но не с самим собой, а поскольку второй элемент пары всегда встречается раньше, его индекс будет первым. Каждое число посещается один раз, а операции с таблицей выполняются за постоянное время, поэтому поиск занимает O(n); цена за это — таблица размером до n элементов.

Алгоритм

Создай пустое отображение значений на индексы.
Для каждого индекса i вычисли need — значение, которое дополняет пару: target минус nums[i].
Если need есть в отображении, верни сохранённый индекс, а затем i.
В противном случае сохрани nums[i] с индексом i и продолжай.

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

Ловушки и крайние случаи

Сохранение числа до поиска его пары. Для [4, 2, 6] и target = 8 число 4 находит само себя, и вы возвращаете [0, 0].
Возврат индексов в неправильном порядке. Если сначала выполнить поиск, а потом сохранить число, индекс из map будет меньше и должен идти первым.
Сортировка массива для использования двух указателей с последующим возвратом позиций в отсортированной копии. Храните исходный индекс каждого значения рядом с ним.
Предположение, что значения положительные или уникальные. В [0, 7, -3, 0] при target = 0 парой будут два нуля: [0, 3].
В Lua и R возвращаются индексы с нумерацией от 1. Вычтите 1 из каждого.

Частые вопросы3

Какова временная сложность задачи Two Sum?

Решение с хеш-таблицей работает за время O(n), поскольку оно проходит по каждому числу один раз, а каждая операция поиска или вставки в среднем занимает постоянное время. Для хеш-таблицы требуется дополнительное пространство O(n). Проверка каждой пары занимает время O(n²) и пространство O(1).

Можно ли решить задачу Two Sum без дополнительной памяти?

Не за линейное время в неотсортированном массиве. При дополнительном расходе памяти O(1) придётся снова проверять каждую пару, что занимает O(n²). Хеш-таблица позволяет получить линейное время за счёт O(n) памяти.

Как Two Sum обрабатывает повторяющиеся числа?

Дубликаты работают, когда ты ищешь пару до сохранения текущего числа. В [7, 3, 7] при target = 14 первая 7 сохраняется с индексом 0, а вторая 7 находит её, что даёт [0, 2]. Одна 7 никогда не образует пару сама с собой: её ещё нет в отображении, когда ты ищешь её.

def twoSum(nums, target):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

nums = [3, 8, 12, 5]
target = 17

Ожидаемый вывод

[2, 3]