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

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

Условие задачи:
Дан массив целых чисел nums длины n и целое число target. Найдите три числа в массиве nums, сумма которых наиболее близка к target. Верните сумму этих трех чисел. Можно предположить, что для каждого входного набора существует ровно одно решение.

Решение:

Python

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # Сначала сортируем массив для удобства поиска
        nums.sort()  # Сортировка позволяет использовать метод двух указателей
        
        # Инициализируем переменную для хранения ближайшей суммы
        closest_sum = float('inf')  # Бесконечность как начальное значение
        
        # Проходим по каждому элементу массива, рассматривая его как первый элемент тройки
        for i in range(len(nums) - 2):  # До len(nums) - 2, так как нужны еще два элемента
            left, right = i + 1, len(nums) - 1  # Указатели на два других элемента
            
            while left < right:  # Пока указатели не встретились
                current_sum = nums[i] + nums[left] + nums[right]  # Текущая сумма трех элементов
                
                # Если текущая сумма ближе к цели, чем предыдущая ближайшая сумма, обновляем её
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum
                
                # Двигаем указатели в зависимости от того, больше или меньше текущая сумма цели
                if current_sum < target:
                    left += 1  # Увеличиваем левый указатель, чтобы увеличить сумму
                elif current_sum > target:
                    right -= 1  # Уменьшаем правый указатель, чтобы уменьшить сумму
                else:
                    # Если текущая сумма равна цели, возвращаем её сразу (она оптимальна)
                    return current_sum
        
        # Возвращаем ближайшую сумму после завершения цикла
        return closest_sum

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

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

Инициализация переменной closest_sum:
Переменная closest_sum используется для хранения текущей ближайшей суммы к целевому значению target. Начальное значение задается как бесконечность (float('inf')), чтобы любая реальная сумма была ближе к цели.

Основной цикл:
Мы проходим по каждому элементу массива, рассматривая его как первый элемент тройки. Для каждого такого элемента мы используем два указателя (left и right) для поиска двух других элементов.

Метод двух указателей:
Указатель left начинается сразу после текущего элемента i, а указатель right начинается с конца массива.

Мы вычисляем текущую сумму трех элементов (current_sum) и проверяем, насколько она близка к целевому значению target.

Если текущая сумма ближе к цели, чем ранее найденная ближайшая сумма, мы обновляем closest_sum.

Движение указателей:
Если текущая сумма меньше цели, мы увеличиваем левый указатель (left += 1), чтобы увеличить сумму.

Если текущая сумма больше цели, мы уменьшаем правый указатель (right -= 1), чтобы уменьшить сумму.

Если текущая сумма равна цели, мы немедленно возвращаем её, так как это оптимальное решение.

Возврат результата:
После завершения всех итераций возвращается значение closest_sum, которое представляет собой сумму трех чисел, наиболее близкую к целевому значению.

Пример работы программы:

Входные данные:
nums = [-1, 2, 1, -4]
target = 1

Выходные данные: 2

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