PrepBro
← Назад к вопросам

Три суммы

2.3 Middle🔥 121 комментариев
#Теория тестирования

Условие

Дан массив чисел. Найдите все уникальные тройки, сумма которых равна нулю.

Пример

Вход: [-1, 0, 1, 2, -1, -4] Выход: [[-1, -1, 2], [-1, 0, 1]]

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение: Алгоритм "Три суммы"

Подход к решению

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

Шаги алгоритма

  1. Сортировка массива — упорядочиваем элементы для упрощения логики избежания дубликатов
  2. Внешний цикл — итерируем по каждому элементу как первого элемента тройки
  3. Пропуск дубликатов — если текущее число уже обработано, пропускаем
  4. Двухпоказательный поиск — используем левый и правый указатели для поиска двух элементов, дополняющих текущий
  5. Сходимость поиска — если сумма мала, двигаем левый указатель; если велика, двигаем правый

Реализация на Python

def threeSum(nums):
    """
    Найти все уникальные тройки, сумма которых равна нулю.
    
    Args:
        nums: List[int] - массив целых чисел
    
    Returns:
        List[List[int]] - список уникальных троек
    """
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        # Оптимизация: если число положительное, сумма не может быть 0
        if nums[i] > 0:
            break
        
        # Пропускаем дубликаты
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        target = -nums[i]
        left = i + 1
        right = n - 1
        
        while left < right:
            current_sum = nums[left] + nums[right]
            
            if current_sum == target:
                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 current_sum < target:
                left += 1
            else:
                right -= 1
    
    return result

Примеры использования

# Пример 1: Базовый случай
result = threeSum([-1, 0, 1, 2, -1, -4])
print(result)  # [[-1, -1, 2], [-1, 0, 1]]

# Пример 2: Массив с нулями
result = threeSum([0, 0, 0, 0])
print(result)  # [[0, 0, 0]]

# Пример 3: Нет решений
result = threeSum([1, 2, 3])
print(result)  # []

# Пример 4: Отрицательные числа
result = threeSum([-2, 0, 1, 1, 2])
print(result)  # [[-2, 0, 2], [-2, 1, 1]]

Анализ сложности

  • Временная сложность: O(n²) — внешний цикл O(n) + двухпоказательный поиск O(n), сортировка O(n log n)
  • Пространственная сложность: O(1) при исключении места для результата, или O(n) с учетом места для результата

Ключевые моменты реализации

  1. Избежание дубликатов — критично проверять на дубликаты на всех уровнях
  2. Граничные условия — обработка пустого массива, массива с менее чем 3 элементами
  3. Оптимизация — если числа положительны, дальнейший поиск невозможен
  4. Корректность — алгоритм гарантирует нахождение всех уникальных троек без пропусков

Этот алгоритм часто встречается на собеседованиях и является хорошей практикой для работы с двухпоказательным методом поиска.