Решение задачи #18. Python LeetCode, 4Sum

Задача относится к алгоритмам и структуре данных. Надо найти все уникальные четверки целых чисел из заданного массива nums, сумма которых равна целевому значению target. Четверки должны состоять из элементов с различных индексов, а результат не должен содержать дубликатов. Задача требует эффективного поиска и обработки повторяющихся значений.

Вариант решения задачи на Python с LeetCode

Категория: Алгоритмы.
Название задачи: 4sum.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Дан массив nums из n целых чисел. Верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]], таких что:

0 <= a, b, c, d < n
Индексы a, b, c и d попарно различны.
Сумма nums[a] + nums[b] + nums[c] + nums[d] равна target.
Вы можете вернуть ответ в любом порядке.

Решение:

Python

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []  # Здесь будем хранить результат — все уникальные четверки
        nums.sort()  # Сортируем массив для удобства работы с дубликатами и двухуказательным методом
        n = len(nums)

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

            for j in range(i + 1, n):  # Второй элемент четверки
                # Пропускаем дубликаты для второго элемента
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue

                # Двухуказательный метод для поиска оставшихся двух чисел
                left = j + 1
                right = n - 1

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

                    if total == target:
                        res.append([nums[i], nums[j], nums[left], nums[right]])

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

                        # Переходим к следующей паре
                        left += 1
                        right -= 1

                    elif total < target:
                        left += 1  # Увеличиваем сумму, двигая left вправо
                    else:
                        right -= 1  # Уменьшаем сумму, двигая right влево

        return res

Объяснение кода

Это расширение задачи Two Sum → Three Sum → Four Sum. Мы хотим найти все уникальные четверки чисел, сумма которых равна заданному target.

Сортировка:
Чтобы можно было легко убирать дубликаты и использовать двухуказательный метод.

Два внешних цикла:
i — первый элемент четверки.
j — второй элемент четверки.
После выбора этих двух элементов мы используем двухуказательный метод (left, right) для поиска оставшихся двух чисел.

Удаление дубликатов:
Проверяем, не повторяются ли значения предыдущих итераций для i и j.
Также пропускаем повторяющиеся left и right, если они уже были учтены.

Двухуказательный метод:
Если текущая сумма равна target — добавляем четверку в результат.
Если меньше — двигаем left вправо.
Если больше — двигаем right влево.

Сложность алгоритма

Временная сложность:
O(n^3) — из-за трёх вложенных циклов (i, j, и двухуказательный поиск).

Пространственная сложность:
O(1) дополнительной памяти (если игнорировать память под результат).

Мы рассмотрели пример решения, который был принят и засчитан платформой как правильный, но вы можете найти свой способ решения задачи, возможно лучше.

Источник решения: hdhai.com