Сумма трёх чисел: разбор задачи

Почему эта задача важна?

Задача "Сумма трёх чисел" позволяет оценить:

• 🧠 Умение оптимизировать перебор в задачах поиска комбинаций
• ⚡ Навыки работы с указателями и отсортированными массивами
• 🎯 Способность обрабатывать дубликаты и поддерживать уникальность результатов
• 🔍 Понимание компромиссов между временем и памятью в алгоритмах

Постановка задачи

Формулировка:

Дан массив целых чисел nums. Верните все возможные тройки чисел [nums[i], nums[j], nums[k]], где nums[i] + nums[j] + nums[k] = 0, и индексы i, j и k различны. Результат не должен содержать повторяющихся троек чисел. Вы можете вернуть тройки в любом порядке.

Примеры:

// Первый пример ✅
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Объяснение:
nums[0] + nums[4] + nums[3] = (-1) + (-1) + 2 = 0
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0

// Второй пример ✅
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
Объяснение: Только одна тройка [0, 0, 0], сумма которой равна 0.

// Третий пример ✅
Input: nums = []
Output: []
Объяснение: Пустой массив не содержит троек.

Ограничения:

• 0 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

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

Решение 1: Наивный подход (перебор всех троек) 🔍

function threeSum(nums) {
  const result = [];
  const seen = new Set();
  
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        // Проверяем, что сумма равна нулю
        if (nums[i] + nums[j] + nums[k] === 0) {
          // Сортируем тройку для обеспечения уникальности
          const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
          const key = triplet.join(',');
          
          // Добавляем только если эта тройка еще не была найдена
          if (!seen.has(key)) {
            result.push(triplet);
            seen.add(key);
          }
        }
      }
    }
  }
  
  return result;
}

Анализ решения:

✅ Простая реализация и понятная логика

✅ Не требует предварительной сортировки массива

❌ Временная сложность O(n³), где n - размер массива

❌ Неэффективен для больших массивов

Решение 2: Хеш-таблица (улучшенный подход) 📚

function threeSum(nums) {
  const result = [];
  const seen = new Set();
  
  for (let i = 0; i < nums.length; i++) {
    // Множество для хранения чисел, которые мы уже видели
    const complements = new Set();
    
    for (let j = i + 1; j < nums.length; j++) {
      // Вычисляем необходимое третье число
      const complement = -nums[i] - nums[j];
      
      if (complements.has(complement)) {
        // Формируем и сортируем тройку для обеспечения уникальности
        const triplet = [nums[i], nums[j], complement].sort((a, b) => a - b);
        const key = triplet.join(',');
        
        // Добавляем только если эта тройка еще не была найдена
        if (!seen.has(key)) {
          result.push(triplet);
          seen.add(key);
        }
      }
      
      // Добавляем текущее число в множество
      complements.add(nums[j]);
    }
  }
  
  return result;
}

Характеристики:

✅ Улучшенная временная сложность O(n²)

✅ Не требует полной сортировки массива

❌ Требует дополнительную память для хеш-таблиц

❌ Обработка дубликатов всё ещё сложна

Решение 3: Сортировка и два указателя (оптимальное решение) 🚀

function threeSum(nums) {
  const result = [];
  
  // Сортируем массив
  nums.sort((a, b) => a - b);
  
  for (let i = 0; i < nums.length - 2; i++) {
    // Пропускаем дубликаты для первого элемента
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    
    let left = i + 1;
    let right = nums.length - 1;
    
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      
      if (sum < 0) {
        // Если сумма меньше нуля, увеличиваем левый указатель
        left++;
      } else if (sum > 0) {
        // Если сумма больше нуля, уменьшаем правый указатель
        right--;
      } else {
        // Нашли тройку с нулевой суммой
        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--;
      }
    }
  }
  
  return result;
}

Преимущества и недостатки:

✅ Оптимальная временная сложность O(n²)

✅ Эффективно обрабатывает дубликаты

✅ Не требует дополнительных хеш-таблиц для уникальности

❌ Требует предварительной сортировки массива O(n log n)

Решение 4: Оптимизированный подход с хеш-таблицей 🔧

function threeSum(nums) {
  const result = [];
  
  // Сортируем массив для упрощения удаления дубликатов
  nums.sort((a, b) => a - b);
  
  for (let i = 0; i < nums.length - 2; i++) {
    // Пропускаем дубликаты для первого элемента
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    
    // Если текущий элемент положительный, то сумма трех положительных
    // чисел не может быть равна нулю
    if (nums[i] > 0) break;
    
    // Используем хеш-таблицу для поиска пар
    const seen = new Set();
    
    for (let j = i + 1; j < nums.length; j++) {
      // Пропускаем дубликаты для второго элемента
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      
      const complement = -nums[i] - nums[j];
      
      if (seen.has(complement)) {
        result.push([nums[i], complement, nums[j]]);
        
        // Пропускаем дубликаты для третьего элемента
        while (j + 1 < nums.length && nums[j] === nums[j + 1]) j++;
      }
      
      seen.add(nums[j]);
    }
  }
  
  return result;
}

Особенности:

✅ Хорошая временная сложность O(n²)

✅ Комбинирует преимущества сортировки и хеш-таблицы

✅ Содержит оптимизации для раннего выхода

❌ Сложнее в реализации и отладке

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Сортировка + два указателя - оптимальный выбор по простоте и эффективности
   • 📝 Хеш-таблица может быть полезна, если нужно сохранить исходный порядок
   • 🧮 Избегайте наивного подхода с тройным вложенным циклом

2. Важные моменты:

   • 📝 Обработка дубликатов - ключевой аспект задачи
   • 🔄 Эффективное использование сортировки для устранения дубликатов
   • 📊 Раннее прерывание (например, если первый элемент > 0)

Распространённые ошибки

1. 🤦‍♂️ Неправильная обработка дубликатов, приводящая к повторяющимся тройкам
2. 😅 Некорректная проверка индексов (i != j != k вместо i < j < k)
3. 🐛 Отсутствие оптимизаций, делающих алгоритм медленным на больших входных данных

Оптимизации

Дополнительные проверки для раннего выхода

function threeSum(nums) {
  const result = [];
  
  // Проверка краевых случаев
  if (nums.length < 3) return result;
  
  // Сортируем массив
  nums.sort((a, b) => a - b);
  
  // Если наименьший элемент положительный, 
  // то невозможно получить сумму 0
  if (nums[0] > 0) return result;
  
  for (let i = 0; i < nums.length - 2; i++) {
    // Пропускаем дубликаты
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    
    // Если текущий элемент положительный, дальнейший поиск бессмыслен
    if (nums[i] > 0) break;
    
    // Если даже сумма трех наименьших элементов > 0, то дальнейший поиск бессмыслен
    if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
    
    // Если сумма текущего элемента и двух наибольших < 0, 
    // то с этим i невозможно получить 0
    if (nums[i] + nums[nums.length - 2] + nums[nums.length - 1] < 0) continue;
    
    let left = i + 1;
    let right = nums.length - 1;
    
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      
      if (sum < 0) {
        left++;
      } else if (sum > 0) {
        right--;
      } else {
        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--;
      }
    }
  }
  
  return result;
}

Оптимизация для часто встречающихся чисел

function threeSum(nums) {
  // Создаем частотный словарь
  const count = new Map();
  for (const num of nums) {
    count.set(num, (count.get(num) || 0) + 1);
  }
  
  // Получаем уникальные числа
  const uniqueNums = [...count.keys()].sort((a, b) => a - b);
  const result = [];
  
  // Обрабатываем специальный случай с тремя нулями
  if (count.get(0) >= 3) {
    result.push([0, 0, 0]);
  }
  
  for (let i = 0; i < uniqueNums.length; i++) {
    const a = uniqueNums[i];
    
    // Пропускаем положительные числа как первый элемент
    if (a > 0) break;
    
    for (let j = i; j < uniqueNums.length; j++) {
      const b = uniqueNums[j];
      
      // Нужно проверить, достаточно ли у нас таких чисел
      if (a === b && count.get(a) < 2) continue;
      
      const c = -a - b;
      
      // Если c меньше b, мы уже обработали эту тройку
      if (c < b) continue;
      
      // Проверяем, есть ли c в нашем словаре
      if (count.has(c)) {
        // Проверяем, достаточно ли у нас таких чисел
        if (c === a && c === b && count.get(c) < 3) continue;
        if ((c === a || c === b) && count.get(c) < 2) continue;
        
        result.push([a, b, c]);
      }
    }
  }
  
  return result;
}

Визуализация алгоритма с двумя указателями

Рассмотрим процесс решения на примере nums = [-1, 0, 1, 2, -1, -4]:

1. Сначала сортируем массив: [-4, -1, -1, 0, 1, 2]

2. Начинаем с первого элемента -4:

   • Устанавливаем указатели: left = 1, right = 5
   • Вычисляем сумму: -4 + (-1) + 2 = -3 < 0, поэтому двигаем left++
   • Новые указатели: left = 2, right = 5
   • Вычисляем сумму: -4 + (-1) + 2 = -3 < 0, поэтому двигаем left++
   • Новые указатели: left = 3, right = 5
   • Вычисляем сумму: -4 + 0 + 2 = -2 < 0, поэтому двигаем left++
   • Новые указатели: left = 4, right = 5
   • Вычисляем сумму: -4 + 1 + 2 = -1 < 0, поэтому двигаем left++
   • Теперь left = 5, right = 5, указатели встретились, переходим к следующему элементу

3. Переходим ко второму элементу -1:

   • Устанавливаем указатели: left = 2, right = 5
   • Вычисляем сумму: -1 + (-1) + 2 = 0, нашли тройку [-1, -1, 2]
   • Двигаем оба указателя: left = 3, right = 4
   • Вычисляем сумму: -1 + 0 + 1 = 0, нашли тройку [-1, 0, 1]
   • Двигаем оба указателя: left = 4, right = 3
   • Указатели пересеклись, переходим к следующему элементу

4. Переходим к третьему элементу -1, но это дубликат, пропускаем

5. Переходим к четвертому элементу 0:

   • Устанавливаем указатели: left = 4, right = 5
   • Вычисляем сумму: 0 + 1 + 2 = 3 > 0, поэтому двигаем right--
   • Теперь left = 4, right = 4, указатели встретились, завершаем

6. Итоговый результат: [[-1, -1, 2], [-1, 0, 1]]

Заключение

При решении задачи "Сумма трёх чисел" важно помнить:

• 🤹‍♂️ Подход с сортировкой и двумя указателями обеспечивает оптимальный баланс между простотой и эффективностью
• 📊 Правильная обработка дубликатов критически важна для корректного результата
• 🧠 Различные оптимизации, такие как ранняя проверка условий, могут значительно ускорить алгоритм

Эта задача демонстрирует, как использование правильных техник (сортировка + два указателя) позволяет эффективно решать комбинаторные задачи, которые на первый взгляд требуют полного перебора. 🌟