16. 3Sum

Задача

Дан массив целых чисел nums. Верните все уникальные тройки, сумма которых равна нулю (без повторяющихся троек).

Примеры

Пример 1

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Пояснение

Уникальные тройки с суммой 0: [-1,0,1] и [-1,-1,2]. Порядок вывода не важен.

Пример 2

Input: nums = [0,1,1]
Output: []

Пояснение

Единственная возможная тройка не даёт в сумме 0.

Пример 3

Input: nums = [0,0,0]
Output: [[0,0,0]]

Пояснение

Единственная возможная тройка даёт в сумме 0.

Решение

Решение

/**
 * Временная сложность: O(n²)
 * - Сортировка: O(n log n)
 * - Внешний цикл: O(n)
 * - Внутренний цикл (два указателя): O(n)
 * - Итого: O(n log n) + O(n²) = O(n²)
 * 
 * Пространственная сложность: O(1) или O(n)
 * - O(1) если не учитывать результирующий массив
 * - O(n) если учитывать результирующий массив и сортировку (в зависимости от реализации)
 * 
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
    nums.sort((a, b) => a - b); // Сортируем массив
    const result = [];
 
    for (let i = 0; i < nums.length - 2; i++) {
        // Пропускаем дубликаты для первого элемента
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
 
        // Оптимизация: если текущий элемент положительный,
        // то сумма трех положительных чисел не может быть 0
        if (nums[i] > 0) {
            break;
        }
 
        let left = i + 1;
        let right = nums.length - 1;
 
        while (left < right) {
            const currentSum = nums[i] + nums[left] + nums[right];
 
            if (currentSum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
 
                // Пропускаем дубликаты для левого указателя
                while (left < right && nums[left] === nums[left + 1]) {
                    left++;
                }
 
                // Пропускаем дубликаты для правого указателя
                while (left < right && nums[right] === nums[right - 1]) {
                    right--;
                }
 
                // Двигаем оба указателя
                left++;
                right--;
 
            } else if (currentSum < 0) {
                left++; // Нужна большая сумма
            } else {
                right--; // Нужна меньшая сумма
            }
        }
    }
 
    return result;
}