4. Three Sum

«Усложнение задачи лишь на один шаг часто требует полной смены парадигмы: там, где не справляется грубая память хеш-таблицы, побеждает строгий порядок сортировки и геометрия встречных указателей».
— Брайан Керниган

LeetCode 15. 3Sum (Medium / Core)

Дан целочисленный массив nums. Необходимо найти все уникальные тройки элементов [nums[i], nums[j], nums[k]], такие что:
$$nums[i] + nums[j] + nums[k] = 0$$
Индексы $i, j, k$ должны быть попарно различны ($i \ne j, i \ne k, j \ne k$), а итоговый набор троек не должен содержать дубликатов.

Эта задача — естественная эволюция Two Sum (3. Two Sum). Однако добавление всего одного слагаемого кардинально меняет правила игры:

• Попытка использовать map упирается в необходимость громоздкой дедупликации троек и огромный расход памяти.
• Оптимальным становится алгоритм с предварительной сортировкой и техникой двух встречных указателей (2. Типовые операции и приёмы).

Формулировка и уточнения требований

Пример:

Вход:  nums = [-1, 0, 1, 2, -1, -4]
Вывод: [[-1, -1, 2], [-1, 0, 1]]
Объяснение: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
nums[4] + nums[0] + nums[3] = (-1) + (-1) + 2 = 0
Дублирующиеся комбинации исключены.

Визуальный Walk-Through: Сортировка + Два встречных указателя

Бытовая модель: представьте весы с чашами. Мы сортируем массив от меньшего к большему. Фиксируем первый гирьку i. Теперь нам нужно уравновесить её двумя другими гирьками j (самая легкая из оставшихся, слева) и k (самая тяжелая, справа).
Если сумма слишком мала — сдвигаем j вправо (берем потяжелее). Если слишком велика — сдвигаем k влево (берем полегче).

flowchart TD
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc

    Start["1. Сортировка среза: slices.Sort(nums)<br>nums = [-4, -1, -1, 0, 1, 2]"]:::entry --> Fix["2. Фиксируем i от 0 до n-3<br>Если nums[i] > 0 -> BREAK (сумма > 0)"]:::accent

    Fix --> Pointers["3. Расставляем указатели:<br>left = i + 1, right = len - 1"]:::process

    Pointers --> Calc["Вычисляем sum = nums[i] + nums[left] + nums[right]"]:::process
    Calc --> Check{"sum == 0?"}:::warning

    Check -->|"sum == 0"| Match["Тройка найдена!<br>Добавляем в результат.<br>Пропускаем дубликаты left и right"]:::success
    Check -->|"sum < 0"| MoveLeft["Слишком мало:<br>left++"]:::process
    Check -->|"sum > 0"| MoveRight["Слишком много:<br>right--"]:::process

    Match --> Loop{"left < right?"}:::warning
    MoveLeft --> Loop
    MoveRight --> Loop
    Loop -->|"Да"| Calc
    Loop -->|"Нет"| NextI["Переход к следующему i<br>(пропуск дубликатов nums[i] == nums[i-1])"]:::accent
  

Наивное решение: Кубический брутфорс $O(N^3)$

func threeSumBrute(nums []int) [][]int {
    n := len(nums)
    var res [][]int
    // Без сортировки сложно отсеять дубликаты троек
    slices.Sort(nums) 

    for i := 0; i < n-2; i++ {
        if i > 0 && nums[i] == nums[i-1] { continue }
        for j := i + 1; j < n-1; j++ {
            if j > i+1 && nums[j] == nums[j-1] { continue }
            for k := j + 1; k < n; k++ {
                if k > j+1 && nums[k] == nums[k-1] { continue }
                if nums[i]+nums[j]+nums[k] == 0 {
                    res = append(res, []int{nums[i], nums[j], nums[k]})
                }
            }
        }
    }
    return res
}

При $N = 3000$ это около $4.5 \cdot 10^9$ итераций, гарантированный Time Limit Exceeded.

Оптимальное решение: $O(N^2)$ без дополнительной памяти

package main

import (
    "slices"
)

func threeSum(nums []int) [][]int {
    n := len(nums)
    if n < 3 {
        return [][]int{}
    }

    // Сортировка на месте за O(N log N)
    slices.Sort(nums)

    res := make([][]int, 0)

    for i := 0; i < n-2; i++ {
        // Досрочный выход: если наименьшее число тройки > 0, сумма 0 невозможна
        if nums[i] > 0 {
            break
        }

        // Пропуск дубликатов первого элемента тройки
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }

        target := -nums[i]
        left, right := i+1, n-1

        for left < right {
            sum := nums[left] + nums[right]
            switch {
            case sum == target:
                res = append(res, []int{nums[i], nums[left], nums[right]})

                // Пропускаем дубликаты второго элемента
                for left < right && nums[left] == nums[left+1] {
                    left++
                }
                // Пропускаем дубликаты третьего элемента
                for left < right && nums[right] == nums[right-1] {
                    right--
                }

                left++
                right--
            case sum < target:
                left++
            default:
                right--
            }
        }
    }

    return res
}

Mechanical Sympathy: Архитектура кэша и память

1. In-place сортировка: slices.Sort (начиная с Go 1.21) использует алгоритм pdqsort (Pattern-Defeating Quicksort). Он работает непосредственно в базовом массиве среза, не требуя аллокаций памяти в куче.
2. Линейное сканирование (Hardware Prefetching): Внутренний цикл с указателями left и right перемещается строго последовательно по непрерывной памяти. Процессорные кэш-линии (64 байта) утилизируются на 100%, не вызывая штрафных циклов ожидания памяти.
3. Хеш-карта vs Сортировка: Решение через map потребовало бы хранить тройки в виде ключа map[[3]int]struct{} для дедупликации, что породило бы тысячи мелких объектов в куче и вызвало тяжелейший оверхед сборщика мусора (GC).

Сравнение Two Sum и 3Sum

Резюме

3Sum учит инженера дисциплине управления дубликатами и демонстрирует превосходство механической непрерывности памяти над абстрактными хэш-таблицами.

В следующей лекции мы разберем алгоритм, который решает задачу поиска непрерывного отрезка с максимальной суммой за один проход — легендарный алгоритм Кадане: 5. Maximum Subarray (Kadane).