Поиск дубликатов в массиве: разбор задачи

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

Задача на поиск дубликатов позволяет оценить:

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

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

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

Дан массив целых чисел. Нужно определить, есть ли в нём повторяющиеся элементы.

Примеры:

// Первый пример ✅
Input: nums = [1, 2, 3, 3]
Output: true // число 3 встречается дважды

// Второй пример ❌
Input: nums = [1, 2, 3, 4]
Output: false // каждое число встречается только один раз

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

Решение 1: Перебор всех пар (базовый подход)

function containsDuplicate(nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) {
        return true
      }
    }
  }
  return false
}

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

✅ Простая реализация

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

❌ Временная сложность O(n²)

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

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

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

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

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

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

Решение 2: Сортировка массива 📊

function containsDuplicate(nums) {
  nums.sort((a, b) => a - b)

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) {
      return true
    }
  }
  return false
}

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

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

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

❌ Изменяет исходный массив

❌ Есть более быстрые решения

Решение 3: Использование множества (Set)

function containsDuplicate(nums) {
  const seen = new Set()

  for (const num of nums) {
    if (seen.has(num)) {
      return true
    }
    seen.add(num)
  }
  return false
}

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

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

✅ Чистая и понятная реализация

✅ Не изменяет исходный массив

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

Решение 4: Использование объекта 🗺️

function containsDuplicate(nums) {
  const frequency = {}

  for (const num of nums) {
    if (frequency[num]) {
      return true
    }
    frequency[num] = 1
  }
  return false
}

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

✅ Удобно для подсчёта частоты элементов

✅ Понятная логика работы

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

❌ Set обычно эффективнее для простого поиска

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

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

   • 🐌 Простой перебор подходит для маленьких массивов
   • 🚀 Set оптимален для больших наборов данных
   • 📊 Сортировка полезна при ограничениях по памяти

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

   • 📝 Проверка пустого массива
   • ➖ Обработка отрицательных чисел
   • 💥 Учёт возможного переполнения

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

1. 🤦‍♂️ Отсутствие проверки пустого массива
2. 😅 Неправильная обработка отрицательных чисел
3. 🐌 Использование неоптимального решения без необходимости

Оптимизации

Оптимизация для небольших массивов

function containsDuplicate(nums) {
  if (nums.length < 10) {
    for (let i = 0; i < nums.length; i++) {
      for (let j = i + 1; j < nums.length; j++) {
        if (nums[i] === nums[j]) return true
      }
    }
    return false
  }

  return new Set(nums).size !== nums.length
}

Эффективная проверка

function containsDuplicate(nums) {
  if (!nums || nums.length <= 1) return false

  const max = Math.max(...nums)
  const min = Math.min(...nums)
  if (max - min + 1 < nums.length) return true

  return new Set(nums).size !== nums.length
}

Заключение

При решении задачи важно помнить:

• 🤹‍♂️ Каждый подход имеет свои преимущества и недостатки
• 📊 Необходимо учитывать требования к памяти и времени
• 🧠 Выбор решения должен быть обоснован условиями задачи

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