4Sum

Q: Какова временная сложность 4Sum?

O(n³). Два цикла выбирают около n²/2 пар (i, j) , и для каждой выполняется один проход двумя указателями длиной не более n шагов; сортировка O(n log n) на этом фоне незначительна.

Q: Как обобщить 4Sum до kSum?

Напиши kSum(nums, target, k) для отсортированного списка. При k = 2 функция выполняет проход двумя указателями. При большем k она перебирает первое значение, пропускает повторы и вызывает себя с k-1 и target - nums[i] для значений справа. Каждый уровень добавляет множитель n, поэтому сложность kSum составляет O(n^(k-1)).

Q: Можно ли решить задачу 4Sum за O(n²)?

Можно сгруппировать n²/2 сумм пар в хеш-таблице и сопоставить каждую пару с парами, сумма которых равна target минус сумма этой пары. Это быстро, когда у немногих пар одинаковая сумма, но для одной суммы может быть O(n²) пар, поэтому в худшем случае это не лучше, чем O(n³).

СреднеДва указателя Сортировка

+10

Дан список целых чисел nums и целое число target. Верните все четверки [a, b, c, d], в которых четыре значения находятся на четырех разных позициях в nums и в сумме дают target. Записывайте значения каждой четверки в неубывающем порядке. Если те же четыре значения можно выбрать с разных позиций, четверка все равно должна появиться только один раз. Отсортируйте ответ сначала по первому значению, затем по второму, затем по третьему. Если подходящих четверок нет, верните пустой список.

Функция

fourSum(nums: integer-array, target: integer) → integer-2d-array

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

Ограничения

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
Сумма любых четырёх значений находится в диапазоне от -4 × 10⁸ до 4 × 10⁸, поэтому она помещается в 32-битное целое число.
Четверки, содержащие одни и те же четыре значения, считаются одной.

Примеры

Ввод: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Вывод: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Пояснение: Сумма каждой из четырёх четвёрок равна 1, например -3 + (-1) + 2 + 3. Сначала идут две, начинающиеся с -3, упорядоченные по второму значению: -1 перед 0.

Ввод: nums = [4, 4, 4, 4, 4, 4]target = 16
Вывод: [[4, 4, 4, 4]]
Пояснение: Все 15 вариантов выбора четырёх позиций из шести дают четыре 4, сумма которых равна 16, поэтому [4, 4, 4, 4] встречается один раз.

Ввод: nums = [1, 5, 2, 9]target = 3
Вывод: []
Пояснение: Единственный вариант — все четыре числа, а 1 + 5 + 2 + 9 = 17, а не 3, поэтому ответ — пустой список.

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

Подсчитайте наборы из четырёх позиций, значения которых в сумме дают target, а не различные четверки. Во втором примере их 15. Сможете сделать это за O(n²)?

Подсказки

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

Открыто 0 из 3

Решение

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

Попробуйте каждый набор из четырёх

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

Идея

Сначала отсортируй массив, чтобы значения в позициях i < j < k < l шли в неубывающем порядке и каждая четвёрка записывалась в правильном порядке. Четыре вложенных цикла перебирают все варианты выбора четырёх позиций. Чтобы избежать повторов, цикл переходит к следующей итерации, если в следующей позиции находится значение, которое он уже пробовал на предыдущем шаге. Для шести четвёрок каждый цикл рассматривает только первую позицию, поэтому [4, 4, 4, 4] появляется один раз, а не 15 раз.

Для 200 чисел существует 64,684,950 наборов из четырёх чисел, и это количество растёт примерно в 16 раз при удвоении n.

Алгоритм

Отсортируй nums.
Вложи четыре цикла по i < j < k < l, каждый начиная на одну позицию дальше цикла, в который он вложен.
В каждом цикле пропускай позицию, если она не первая в этом цикле и содержит то же значение, что и предыдущая позиция.
Сохрани [nums[i], nums[j], nums[k], nums[l]], если сумма четырёх чисел равна target. Циклы выдают их в отсортированном порядке.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            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 - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Сортировка, два цикла, два указателя

Идея

Зафиксируй nums[i] и nums[j], и останется задача о паре: найти два значения правее j, сумма которых равна target - nums[i] - nums[j]. В отсортированном списке достаточно одного прохода. Установи lo на j+1, а hi — на последний индекс. Если сумма меньше target, сдвигай lo вправо; если больше — сдвигай hi влево.

Каждый сдвиг исключает значение, которое не входит ни в один ответ. Если сумма слишком мала, даже наибольшего оставшегося значения, nums[hi], недостаточно для nums[lo], поэтому nums[lo] можно исключить. Слишком большая сумма исключает nums[hi] по аналогичной причине. Для одной пары (i, j) требуется не более n сдвигов, поэтому n²/2 пар дают сложность O(n³).

В первом примере, когда i указывает на -3, а j — на -1, lo сдвигается с 0 через 1 к 2, где -3 + (-1) + 2 + 3 = 1.

Алгоритм

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

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

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

Пропускать j каждый раз, когда nums[j] равно nums[j-1]. При j = i+1 сравнивается значение, которое использует i, поэтому для [2, 2, 2, 2, 2] с целевым значением 8 теряется [2, 2, 2, 2].
Копировать ранний выход из 3Sum nums[i] > target. Для [-5, -4, -3, -2, -1] и целевого значения -10 цикл останавливается на -5 и пропускает [-4, -3, -2, -1].
Списки короче четырёх элементов. Если чисел одно или два, n-3 отрицательно: 0..<(n - 3) приводит к ошибке в Swift, а n - 3 для usize в Rust вызывает переполнение вниз. Сначала возвращайте пустой список.
Собирать четверки в хеш-множество и возвращать их без сортировки.

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

Какова временная сложность 4Sum?

O(n³). Два цикла выбирают около n²/2 пар (i, j), и для каждой выполняется один проход двумя указателями длиной не более n шагов; сортировка O(n log n) на этом фоне незначительна.

Как обобщить 4Sum до kSum?

Напиши kSum(nums, target, k) для отсортированного списка. При k = 2 функция выполняет проход двумя указателями. При большем k она перебирает первое значение, пропускает повторы и вызывает себя с k-1 и target - nums[i] для значений справа. Каждый уровень добавляет множитель n, поэтому сложность kSum составляет O(n^(k-1)).

Можно ли решить задачу 4Sum за O(n²)?

Можно сгруппировать n²/2 сумм пар в хеш-таблице и сопоставить каждую пару с парами, сумма которых равна target минус сумма этой пары. Это быстро, когда у немногих пар одинаковая сумма, но для одной суммы может быть O(n²) пар, поэтому в худшем случае это не лучше, чем O(n³).

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

Тест #1

Тест #2

Тест #3

Аргументы

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

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

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