3Sum в Python: разбор задачи с двух указателей

Зачем решать 3Sum на Python

Задача 3Sum — одна из самых популярных на собеседованиях в FAANG. Она учит важному паттерну: зафиксировать один элемент и свести задачу к известной подзадаче. После фиксации одного числа остаётся 2Sum, который решается двумя указателями за O(n). Освоив 3Sum, ты автоматически поймёшь 4Sum и KSum.

Условие задачи

Дан целочисленный массив nums. Нужно вернуть все уникальные тройки [nums[i], nums[j], nums[k]], такие что:

• i != j, i != k, j != k
• nums[i] + nums[j] + nums[k] = 0
• Дубликаты троек запрещены

Пример:

Вход: nums = [-1, 0, 1, 2, -1, -4]
Выход: [[-1, -1, 2], [-1, 0, 1]]

Brute Force: три вложенных цикла

Самое очевидное решение — перебрать все возможные тройки тремя вложенными циклами. Для каждой тройки проверяем сумму, и если она равна нулю — добавляем в результат через множество для уникальности.

def three_sum_brute(nums):
    n = len(nums)
    result = set()
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    # Сортируем тройку для уникальности
                    triplet = tuple(sorted([nums[i], nums[j], nums[k]]))
                    result.add(triplet)
    return [list(t) for t in result]

Сложность: O(n³) по времени, O(m) по памяти, где m — количество троек. На массиве из 1000 элементов это около 166 миллионов операций — слишком медленно для собеседования.

Оптимальное решение: two pointers после сортировки

Ключевая идея: после сортировки массива задача сводится к 2Sum. Фиксируем один элемент nums[i], и ищем два других, сумма которых равна -nums[i]. Два указателя двигаются навстречу друг другу, что даёт O(n²).

Алгоритм по шагам

1. Сортируем массив
2. Проходим по массиву, фиксируя nums[i]
3. Пропускаем дубликаты фиксированного элемента
4. Ставим left = i + 1, right = n - 1
5. Пока left < right:
   • Если сумма < 0 — двигаем left вправо
   • Если сумма > 0 — двигаем right влево
   • Если сумма = 0 — сохраняем тройку, двигаем оба указателя и пропускаем дубликаты

Реализация на Python

def three_sum(nums):
    nums.sort()  # O(n log n)
    n = len(nums)
    result = []

    for i in range(n - 2):
        # Пропускаем дубликаты фиксированного элемента
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = n - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total < 0:
                left += 1  # Нужна большая сумма
            elif total > 0:
                right -= 1  # Нужна меньшая сумма
            else:
                # Нашли тройку
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1

                # Пропускаем дубликаты слева
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                # Пропускаем дубликаты справа
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1

    return result

Разбор на примере

Возьмём массив [-4, -1, -1, 0, 1, 2]:

• i = 1, nums[i] = -1. Нужна сумма b + c = 1
• left = 2 (указывает на -1), right = 5 (указывает на 2)
• Сумма: -1 + (-1) + 2 = 0 → тройка [-1, -1, 2]
• Двигаем указатели: left = 3 (0), right = 4 (1)
• Сумма: -1 + 0 + 1 = 0 → тройка [-1, 0, 1]
• Дальше left >= right, выходим

Результат: [[-1, -1, 2], [-1, 0, 1]]

Почему пропуск дубликатов важен

Без пропуска дубликатов мы получим одинаковые тройки несколько раз. Например, для [-2, 0, 0, 0, 2, 2]:

• Без пропуска: [-2, 0, 2] появится 6 раз
• С пропуском: один раз

Пропуск дубликатов на всех трёх уровнях (фиксированный элемент, левый указатель, правый указатель) гарантирует уникальность.

Сложность

• Время: O(n²). Сортировка O(n log n) + два указателя O(n²) = O(n²)
• Память: O(1) без учёта выходного массива

Паттерн для других задач

Этот подход обобщается:

• 2Sum — HashMap или two pointers
• 3Sum — фиксируем 1 + two pointers
• 4Sum — фиксируем 2 + two pointers
• KSum — рекурсивное сведение

Когда видишь «тройки», «уникальные комбинации», «сумма равна цели» — сразу думай: сортировка → фиксация → два указателя.

Что делать прямо сейчас

Открой LeetCode, найди задачу 3Sum и реши её на Python, используя код из статьи. Затем попробуй 4Sum — паттерн тот же, только фиксируешь два элемента. Через час ты закрепишь навык, который пригодится на любом техническом собеседовании.