Задачи на массивы на собеседовании: что спрашивают чаще всего

Коротко

Массивы — самая частая тема на собеседованиях. Примерно каждая третья задача так или иначе про них.

Приём 1. Хеш-таблица

Самый частый способ убрать вложенный цикл.

Признак: для каждого элемента вы ищете другой элемент.

Найти пару с заданной суммой

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}                       # значение -> индекс
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

Ключевая мысль: вместо поиска «есть ли где-то дополнение» мы запоминаем виденное. O(n²) превращается в O(n).

Есть ли дубликаты

def has_duplicate(nums: list[int]) -> bool:
    return len(set(nums)) != len(nums)

Однострочник, но на интервью проговорите: множество строится за O(n), память тоже O(n). Если памяти нельзя — придётся сортировать за O(n log n).

Самая длинная последовательность подряд идущих

Задача, где хеш-таблица даёт неочевидный выигрыш.

def longest_consecutive(nums: list[int]) -> int:
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 in s:
            continue                # не начало последовательности
        length = 1
        while x + length in s:
            length += 1
        best = max(best, length)
    return best

Выглядит как квадрат из-за вложенного while, но это O(n): внутренний цикл запускается только для начал последовательностей, и каждый элемент посещается один раз. Это обязательно нужно проговорить вслух — интервьюер почти всегда спрашивает.

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

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

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

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

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

Приём 2. Два указателя

Признак: массив отсортирован (или его можно отсортировать), а ответ — пара или тройка элементов.

Пара в отсортированном массиве

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1               # нужна сумма больше
        else:
            right -= 1              # нужна сумма меньше
    return []

Память O(1) против O(n) у хеш-таблицы — вот за что платим сортировкой.

Сумма трёх чисел

Классика. Фиксируем первый элемент, для оставшихся — два указателя.

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                # пропускаем дубликаты

        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1       # пропускаем дубликаты
    return result

Обработка дубликатов — то, на чём чаще всего валятся. Проговорите её отдельно.

Контейнер с наибольшей водой

def max_area(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        best = max(best, min(height[left], height[right]) * (right - left))
        if height[left] < height[right]:
            left += 1               # двигаем меньшую стенку
        else:
            right -= 1
    return best

Неочевидная часть — почему двигать нужно меньшую стенку. Объяснение: площадь ограничена меньшей высотой, и сдвиг большей стенки только уменьшит ширину, не увеличив высоту.

Приём 3. Скользящее окно

Признак: в условии «непрерывный подмассив» плюс минимум или максимум длины.

Лучшее время купить и продать акции

def max_profit(prices: list[int]) -> int:
    min_price = float('inf')
    best = 0
    for price in prices:
        min_price = min(min_price, price)
        best = max(best, price - min_price)
    return best

Формально это не окно, а один проход с накоплением минимума — но семейство то же: один проход вместо перебора пар.

Максимальная сумма подмассива длины k

def max_sum_of_size(nums: list[int], k: int) -> int:
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]     # пришёл новый, ушёл старый
        best = max(best, window)
    return best

Суть приёма в одной строке: вместо пересчёта суммы окна вычитаем ушедшее и прибавляем пришедшее.

Приём 4. Произведение всех кроме текущего

Отдельная задача, которую любят из-за ограничения «без деления».

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n

    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]           # произведение всего слева

    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]           # произведение всего справа

    return result

Два прохода: слева накапливаем префиксные произведения, справа домножаем на суффиксные. O(n) времени, O(1) дополнительной памяти (результат не считается).

Приём 5. Работа на месте

Признак: «измените массив на месте», «без дополнительной памяти».

Переместить нули в конец

def move_zeroes(nums: list[int]) -> list[int]:
    k = 0
    for x in nums:
        if x != 0:
            nums[k] = x
            k += 1
    while k < len(nums):
        nums[k] = 0
        k += 1
    return nums

Указатель k отмечает позицию для следующего ненулевого элемента. Стандартный приём для всех задач «удалить/переместить элементы на месте».

Удалить дубликаты из отсортированного массива

def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            nums[k] = nums[i]
            k += 1
    return k                        # новая длина

Как быстро выбрать приём

Схема на четыре вопроса:

1. Массив отсортирован? → два указателя или бинарный поиск.
2. Ищем пару или дополнение? → хеш-таблица.
3. Нужен непрерывный подотрезок? → скользящее окно.
4. Много запросов суммы на отрезке? → префиксные суммы.

Если ничего не подошло — почти всегда работает связка «отсортировать и посмотреть, что упростилось».

Типичные ошибки

Забытые дубликаты. В задачах на тройки и пары они ломают ответ чаще всего.

Изменение массива, когда нельзя. Уточните: можно ли сортировать входные данные. Иногда индексы нужно вернуть исходные.

Пустой массив и один элемент. Проверяйте всегда, даже если условие обещает непустой ввод.

Переполнение при сумме. В Python не проблема, в Java и C++ — вполне.

Неверная оценка сложности. Срез nums[i:] внутри цикла стоит O(n) и превращает решение в квадрат.

Что запомнить

• Массивы — самая частая тема, примерно треть всех задач.
• Хеш-таблица убирает вложенный цикл: запоминаем виденное вместо поиска.
• Два указателя работают на отсортированных данных и дают O(1) памяти.
• Скользящее окно: вычитаем ушедшее, прибавляем пришедшее вместо пересчёта.
• Задачи «на месте» решаются указателем записи, идущим следом за указателем чтения.
• Дубликаты и пустой ввод — главные источники провалов.