3Sum

+10

Дан список целых чисел nums. Найдите все тройки [a, b, c] значений, взятых из трёх разных позиций списка nums, для которых a + b + c = 0. Запишите каждую тройку в неубывающем порядке (a ≤ b ≤ c) и укажите каждую уникальную тройку только один раз, даже если её можно получить, выбрав разные позиции. Верните тройки, отсортированные сначала по первому значению, а затем по второму.

Функция

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: список целых чисел, содержащий не менее трёх элементов
Возвращаетinteger-2d-array: каждая уникальная тройка чисел, сумма которых равна 0, отсортированная в неубывающем порядке; список отсортирован

Ограничения

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
Как минимум одна тройка в сумме дает 0.
Две тройки одинаковы, если содержат одни и те же три значения.

Примеры

Ввод: nums = [-2, 0, 1, 1, -1, 2]
Вывод: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Пояснение: -2 + 0 + 2, -2 + 1 + 1 и -1 + 0 + 1 дают 0. [-2, 1, 1] может использовать значение 1 дважды, поскольку число 1 стоит на двух позициях, а [-1, 0, 1] можно составить с любым из этих чисел 1, но оно встречается один раз.

Ввод: nums = [0, 0, 0, 0]
Вывод: [[0, 0, 0]]
Пояснение: Любые три из четырёх нулей в сумме дают 0. Это четыре варианта выбора позиций, но все они дают одну и ту же тройку, поэтому ответ содержит [0, 0, 0] один раз.

+15 скрытых тестов при отправке

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

Тот же шаблон решает задачу 4Sum: зафиксируй два значения и запусти два указателя по остальным. Сможешь написать решение за O(n³) и правильно обработать дубликаты на каждом уровне?

Подсказки

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

Открыто 0 из 3

Решение

Есть две причины, по которым задача 3Sum сложнее, чем кажется. Проверка каждой тройки занимает O(n³), а в ответе каждая тройка должна присутствовать только один раз, даже если значения повторяются. Сортировка решает обе проблемы: одинаковые значения оказываются рядом, поэтому повторы можно пропускать, сравнивая соседние элементы, а когда наименьшее значение зафиксировано, для двух остальных возникает задача о сумме пары в отсортированном списке, которую два указателя решают за один проход.

Попробуйте все тройки

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

Идея

Сначала отсортируйте список. Тогда любые три позиции i < j < k дадут значения, которые уже идут по порядку: nums[i] ≤ nums[j] ≤ nums[k], поэтому триплет будет записан правильно сразу же, как только вы его найдёте. Три вложенных цикла перебирают все возможные варианты позиций, поэтому ни один триплет не будет пропущен.

Теперь о повторениях. Первый отсортированный пример — [-2, -1, 0, 1, 1, 2], а для [-1, 0, 1] можно взять 1 с индекса 3 или 4. Поэтому каждый цикл пропускает позицию, значение которой совпадает со значением, которое этот же цикл уже проверял ранее. Таким образом, каждый цикл проверяет каждое уникальное значение ровно один раз, и каждый уникальный триплет появляется ровно один раз, уже в отсортированном порядке. Пропуск сравнивает значение только с предыдущей позицией внутри того же цикла, поэтому в [-2, 1, 1] по-прежнему используются обе единицы.

Проблема — в затратах. Всего получается около n³/6 троек: для 3000 чисел это 4.5 × 10^9 сумм, что намного превышает любое ограничение по времени.

Алгоритм

Отсортируй nums.
Перебирай позиции с помощью цикла по i и пропускай i, когда nums[i] равно nums[i-1].
Внутри него перебирай j, начиная с i+1, и пропускай j, когда j > i+1 и nums[j] равно nums[j-1].
Внутри этого цикла перебирай k, начиная с j+1, применяя то же правило пропуска, и сохраняй [nums[i], nums[j], nums[k]], если сумма этих трёх чисел равна 0.
Верни тройки в том порядке, в котором ты их нашёл. Они уже отсортированы.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

Исправь одно значение, найди пару с помощью хеш-множества

Идея

После того как первое значение nums[i] зафиксировано, нужно найти два следующих значения, сумма которых равна -nums[i]. Это задача Two Sum. Перемещай j вправо от i и храни в множестве значения, которые уже встретились. Для каждого j недостающее значение — это need = -nums[i] - nums[j]. Если need есть в множестве, то сумма [nums[i], need, nums[j]] равна 0. В среднем поиск в множестве занимает O(1), поэтому для одного i требуется O(n), а весь поиск — O(n²).

Сортировка по-прежнему помогает вести учёт. Пропускай i, если его значение совпадает с предыдущим. После совпадения перемещай j дальше всех повторений nums[j]: когда первое и третье значения зафиксированы, среднее значение тоже фиксировано, поэтому ещё одно такое же значение может только повторить ту же тройку. Поскольку need берётся из более ранней позиции отсортированного списка, need ≤ nums[j], и тройка упорядочена. Можно также остановиться, как только nums[i] > 0: два следующих значения не меньше него, поэтому сумма не может быть равна 0.

Один нюанс: когда j движется вправо, nums[j] увеличивается, а need уменьшается, поэтому тройки для одного i будут получаться так, что среднее значение убывает. В [-2, -1, 0, 1, 1, 2] при i = 0 ты находишь [-2, 1, 1] на втором значении 1, а затем [-2, 0, 2] на значении 2. Переверни каждую группу перед тем, как добавить её в ответ. В версиях на C и R отмеченные значения хранятся в массиве с индексами, соответствующими значениям, а не в хеш-множестве; это работает, потому что все значения лежат в диапазоне ±10^5.

Алгоритм

Отсортируй nums.
Для каждого i остановись, когда nums[i] > 0, и пропусти i, если nums[i] равно nums[i-1].
Создай пустое множество. Для каждого j, начиная с i+1, вычисли need = -nums[i] - nums[j]. Если need есть в множестве, добавь в результат [nums[i], need, nums[j]] и перемести j за все копии nums[j].
Добавь nums[j] в множество и перейди к следующему j.
Разверни найденные для этого i тройки и добавь их к ответу.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

Сортировка и использование двух указателей

Идея

Отсортированный порядок может заменить множество. Зафиксируй nums[i], установи lo на i+1, а hi — на последний индекс и проверь nums[i] + nums[lo] + nums[hi]. Если сумма меньше 0, нужно большее значение, поэтому lo сдвигается вправо. Если сумма больше 0, нужно меньшее значение, поэтому hi сдвигается влево. Если сумма равна 0, добавь тройку в результат и сдвинь оба указателя.

Ни одна тройка не теряется. Когда сумма меньше 0, nums[lo] слишком мало даже в паре с наибольшим оставшимся значением — nums[hi], поэтому оно не может образовать пару ни с чем из оставшегося диапазона, и его удаление ничего не теряет. Сумма больше 0 — зеркальный случай: nums[hi] слишком велико даже в паре с наименьшим оставшимся значением. На каждом шаге одно значение удаляется окончательно, поэтому для одного i требуется не более n шагов, а весь поиск занимает O(n²), не считая сортировки и результата, дополнительная память не нужна.

Возьмём отсортированный массив [-2, -1, 0, 1, 1, 2]. При i = 0 (значение -2) lo начинается с -1, а hi — с 2: сумма равна -1, поэтому lo сдвигается к 0. Теперь -2 + 0 + 2 = 0, поэтому добавь в результат [-2, 0, 2], и оба указателя окажутся на двух единицах, которые дают [-2, 1, 1]. При i = 1 (значение -1) значения 0 и 2 дают 1, поэтому hi сдвигается ко второй единице, а -1 + 0 + 1 = 0, и в результат добавляется [-1, 0, 1]. При i = 2 значение 0 ничего не находит, а при i = 3 значение положительное, поэтому поиск прекращается.

Для повторяющихся значений нужны два правила. Пропускай i, если его значение равно предыдущему. После совпадения передвигай lo дальше всех копий использованного значения. Для hi отдельное правило не нужно: когда lo указывает на большее значение, копия прежнего nums[hi] теперь даёт сумму больше 0 и сама сдвигает указатель дальше. Поскольку i проходит различные значения в порядке возрастания, а lo движется только вправо, тройки получаются отсортированными.

Алгоритм

Отсортируй nums.
Для каждого i останавливайся, когда nums[i] > 0, и пропускай i, если nums[i] равно nums[i-1].
Установи lo = i+1 и hi = n-1. Пока lo < hi, сложи nums[i], nums[lo] и nums[hi].
Если сумма меньше 0, сдвинь lo вправо. Если она больше 0, сдвинь hi влево.
Если сумма равна 0, сохрани тройку, сдвинь оба указателя, затем передвинь lo за все копии использованного значения.
Верни тройки. Они уже отсортированы.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

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

Большинство неправильных ответов возникает из-за повторяющихся значений, поэтому проверяй решение на входных данных с такими значениями.

Если пропустить i, когда nums[i] равно nums[i+1], последняя копия каждого значения останется первым элементом, а копии перед ней исчезнут. В [-1, -1, 2] это приводит к потере [-1, -1, 2]. Сравнивай с предыдущей позицией: nums[i-1].
Если остановиться при nums[i] ≥ 0, а не при nums[i] > 0, будет пропущен случай [0, 0, 0].
Удалять повторы в конце, а не пропускать их. Для 3000 нулей цикл с двумя указателями записывает миллионы копий [0, 0, 0] до очистки, а в нескольких языках списки в множестве сравниваются по идентичности, поэтому копии всё равно остаются.
Использовать одну позицию дважды. Вариант с хеш-множеством, которое заранее заполняется всем списком, превращает [-2, 1, 3] в [-2, 1, 1], используя единственную 1 дважды. Ищи значения только в тех позициях, которые ты уже прошёл.
Возвращать тройки не в нужном порядке. Сравнение точное, поэтому вариант с хеш-множеством должен разворачивать каждую группу, а решение, которое собирает тройки в множество, должно отсортировать их в конце.

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

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

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

Как 3Sum избегает дублирующихся троек?

Он сортирует список, поэтому одинаковые значения оказываются рядом. Затем он пропускает первое значение, если оно равно предыдущему, а после каждого совпадения передвигает левый указатель за копии использованного значения. Каждый триплет находится один раз — по первым копиям своих значений, поэтому набор результатов не нужен.

Для задачи 3Sum использовать два указателя или хеш-множество?

Оба алгоритма работают за время O(n²). Для метода двух указателей не нужна дополнительная память, а отсортированный порядок сразу располагает тройки по порядку. Хеш-множество требует O(n) памяти, и нужно следить, чтобы позиции были различными, а результат — отсортированным. Идея с хеш-множеством важна, когда массив нельзя отсортировать, как в задаче Two Sum, где нужно вернуть исходные индексы.

Можно ли решить задачу 3Sum быстрее, чем за O(n²)?

Не намного. Самые известные алгоритмы превосходят n² лишь на несколько логарифмических множителей, а многие результаты о сложности задач в вычислительной геометрии предполагают, что ни один алгоритм не достигает степени n ниже 2. Эти более быстрые алгоритмы — результаты исследований, поэтому на собеседованиях ожидают ответ O(n²).

Python

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

Тестовые случаи

Случай 1

Случай 2

Ввод

nums = [-2, 0, 1, 1, -1, 2]

Ожидается

[[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]

3Sum

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуйте все тройки

Исправь одно значение, найди пару с помощью хеш-множества

Сортировка и использование двух указателей

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

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

Похожие задачи