3Sum

Средняя№15навстречу

Дан массив чисел. Нужно найти все тройки чисел из трёх разных мест массива с суммой 0. Каждая тройка попадает в ответ один раз, даже если её можно собрать из массива несколькими способами. Наш пример: [2, -2, 0, 1, -1, -2] — ответ [-2, 0, 2] и [-1, 0, 1].

15 3SumРазбор · 1×

Пример: [2, -2, 0, 1, -1, -2], после сортировки [-2, -2, -1, 0, 1, 2]. i фиксирует одно число, left и right идут навстречу и ищут два других.

0-21-22-1304152до сортировки2-201-1-2
зафиксированное число nums[i]пара под left и rightещё возможныотброшены или пропущенытройка с суммой 0

Сортируем: [2, -2, 0, 1, -1, -2] становится [-2, -2, -1, 0, 1, 2]. Одинаковые числа теперь стоят рядом

01/59
сначала · назад · пуск · шаг
Скорость
1function threeSum(nums):
2 sort(nums)
3 triples = []
4 for i from 0 to len(nums) - 3:
5 if i > 0 and nums[i] == nums[i - 1]:
6 continue
7 left = i + 1
8 right = len(nums) - 1
9 while left < right:
10 sum = nums[i] + nums[left] + nums[right]
11 if sum < 0:
12 left = left + 1
13 else if sum > 0:
14 right = right - 1
15 else:
16 t = [nums[i], nums[left], nums[right]]
17 add t to triples
18 left = left + 1
19 right = right - 1
20 while left < right and nums[left] == t[1]:
21 left = left + 1
22 return triples
состояние
i
–
nums[i]
–
left
–
right
–
sum
–
t
–
triples
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Зафиксируем одно число, nums[i], — тогда два других должны дать в сумме -nums[i]. В отсортированном массиве это Two Sum II: left и right идут навстречу, и каждый сдвиг отбрасывает число навсегда.
  2. После сортировки одинаковые числа стоят рядом, поэтому повтор легко заметить. Если nums[i] равно предыдущему числу, его тройки уже найдены, и i его пропускает; после найденной тройки left так же перешагивает копии её среднего числа.
  3. Каждая тройка находится один раз — когда i впервые встаёт на её самое маленькое число: цикл перебирает все первые числа, а поиск пары видит все пары правее.

Сложность

Время O(n²): сортировка занимает O(n log n), а потом для каждого из n значений i указатели проходят остаток массива один раз. Память O(1) без учёта ответа: массив сортируем на месте, а для повторов не нужно множество.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.