Пример решения задачи #15. Python LeetCode, 3Sum

Вариант решения задачи на языке программирования Python с LeetCode.
Категория: Алгоритмы.
Название задачи: 3Sum.
Сложность: Средняя.
Статус решения: "Решено".

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

- Индексы удовлетворяют условиям: $i \neq j$, $i \neq k$ и $j \neq k$.
- Сумма элементов тройки равна нулю: $nums[i] + nums[j] + nums[k] = 0$.

Обратите внимание, что набор решений не должен содержать повторяющихся троек.

Решение:

Python

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # Сортируем массив для удобства поиска и исключения дубликатов
        nums.sort()
        result = []  # Результирующий список для хранения троек

        # Проходим по каждому элементу массива
        for i in range(len(nums)):
            # Если текущий элемент больше нуля, то сумма трех чисел не может быть равна нулю,
            # так как массив отсортирован и все последующие элементы будут положительными
            if nums[i] > 0:
                break

            # Пропускаем дубликаты текущего элемента
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # Инициализируем два указателя для поиска пары чисел
            left, right = i + 1, len(nums) - 1

            # Пока левый указатель меньше правого
            while left < right:
                total = nums[i] + nums[left] + nums[right]  # Вычисляем сумму трех чисел

                if total == 0:  # Если сумма равна нулю
                    result.append([nums[i], nums[left], nums[right]])  # Добавляем тройку в результат

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

                    # Двигаем оба указателя к центру
                    left += 1
                    right -= 1

                elif total < 0:  # Если сумма меньше нуля, двигаем левый указатель вправо
                    left += 1
                else:  # Если сумма больше нуля, двигаем правый указатель влево
                    right -= 1

        return result  # Возвращаем результирующий список троек

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

Сортировка массива:
Мы начинаем с сортировки массива nums. Это позволяет нам эффективно использовать метод двух указателей и избегать дубликатов.

Основной цикл:
Мы перебираем каждый элемент массива (nums[i]) и рассматриваем его как первый элемент потенциальной тройки.
Если текущий элемент больше нуля, мы завершаем цикл, так как сумма трех положительных чисел не может быть равна нулю.

Пропуск дубликатов:
Чтобы избежать повторяющихся троек, мы пропускаем одинаковые значения для первого элемента тройки (nums[i]).

Два указателя:
Для каждого выбранного nums[i], мы инициализируем два указателя: left (начинается с i + 1) и right (начинается с конца массива).

Мы вычисляем сумму трех чисел (nums[i] + nums[left] + nums[right]):
Если сумма равна нулю, добавляем тройку в результат и двигаем оба указателя, пропуская дубликаты.
Если сумма меньше нуля, увеличиваем левый указатель (left), чтобы увеличить сумму.
Если сумма больше нуля, уменьшаем правый указатель (right), чтобы уменьшить сумму.

Возврат результата:
После завершения всех итераций возвращаем список уникальных троек.

Пример выполнения:
Входные данные:
nums = [-1, 0, 1, 2, -1, -4]

Выходные данные:
[[-1, -1, 2], [-1, 0, 1]]

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