Массивы и хэш-таблицы

1.

Two Sum

Easy массив хэш-таблица один проход

Дан массив целых чисел nums и число target. Найдите индексы двух элементов, сумма которых равна target. Каждый элемент можно использовать не более одного раза, решение гарантированно единственное. Порядок индексов в ответе не важен.

Ограничения: 2 ≤ nums.length ≤ 10⁴, −10⁹ ≤ nums[i], target ≤ 10⁹.

Пример 1

nums = [2, 7, 11, 15], target = 9
output = [0, 1]      # nums[0] + nums[1] == 9

Пример 2

nums = [3, 2, 4], target = 6
output = [1, 2]

Подсказка

Перебор всех пар — это O(n²). Подумайте наоборот: проходя по массиву, для текущего числа x вам нужен уже встреченный элемент target − x. Где быстрее всего искать «встречалось ли значение и под каким индексом»?

Решение

Один проход с хэш-таблицей seen: значение → индекс. Проверяем, есть ли «напарник» target − x, и только потом добавляем текущий элемент — так элемент не «спарится» сам с собой.

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i

Сложность: время O(n), память O(n).

121.

Best Time to Buy and Sell Stock

Medium массив динамика / один проход

Массив prices — цена акции на каждый день. Выбрать один день для покупки и позже — другой день для продажи. Верните максимально возможную прибыль; если заработать нельзя, верните 0.

Ограничения: 1 ≤ prices.length ≤ 10⁵, 0 ≤ prices[i] ≤ 10⁴.

Пример 1

prices = [7, 1, 5, 3, 6, 4]
output = 5           # купить на 2-й день за 1, продать на 5-й за 6

Пример 2

prices = [7, 6, 4, 3, 1]
output = 0           # цены только падают

Подсказка

Для каждой даты продажи прибыль максимальна, если покупка была по минимальной цене среди всех предыдущих дней. Значит, достаточно одной переменной «минимум слева».

Решение

def max_profit(prices):
    min_price = float("inf")
    best = 0
    for p in prices:
        min_price = min(min_price, p)   # лучшая цена покупки слева
        best = max(best, p - min_price) # лучшая продажа сегодня
    return best

Сложность: время O(n), память O(1).

Вариант на Codewars с той же идеей: Max Profit.

238.

Product of Array Except Self

Medium массив префиксные произведения

Дан массив nums. Верните массив answer, где answer[i] — произведение всех элементов nums, кроме nums[i]. Делить на nums[i] нельзя, алгоритм должен работать за O(n).

Ограничения: 2 ≤ nums.length ≤ 10⁵, гарантированно произведение любой приставки помещается в 32 бита.

Пример 1

nums = [1, 2, 3, 4]
output = [24, 12, 8, 6]

Пример 2

nums = [-1, 1, 0, -3, 3]
output = [0, 0, 9, 0, 0]

Подсказка

Ответ для позиции i = (произведение всего слева от i) × (произведение всего справа от i). Два прохода: слева направо, затем справа налево.

Решение

def product_except_self(nums):
    n = len(nums)
    answer = [1] * n

    left = 1
    for i in range(n):
        answer[i] = left     # произведение элементов слева
        left *= nums[i]

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

    return answer

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

49.

Group Anagrams

Medium массив строки хэш-таблица

Дан массив строк strs. Сгруппируйте анаграммы (слова, составленные из одних и тех же букв в разном порядке) в группы. Порядок групп и строк внутри них не важен.

Ограничения: 1 ≤ strs.length ≤ 10⁴, 0 ≤ strs[i].length ≤ 100, только строчные латинские буквы.

Пример 1

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
output = [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

Пример 2

strs = [""]
output = [[""]]

Подсказка

Нужен «канонический ключ», одинаковый для всех анаграмм. Два варианта: отсортированная строка ("tea" → "aet") или счётчик букв как кортеж из 25 чисел.

Решение

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))   # канонический вид анаграммы
        groups[key].append(s)
    return list(groups.values())

Сложность: время O(n · k log k), память O(n · k), где k — максимальная длина строки. Со счётчиком букв: O(n · k).

239.

Sliding Window Maximum

Hard массив моностек / дек

Дан массив nums и размер окна k. Окно из k элементов сдвигается с левого края массива к правому, по одному элементу за шаг. Для каждой позиции окна выведите его максимум.

Ограничения: 1 ≤ nums.length ≤ 10⁵, 1 ≤ k ≤ nums.length.

Пример 1

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
окна:   [1  3  -1] -3  5  3  6  7  → 3
         1 [3  -1  -3] 5  3  6  7  → 3
         1  3 [-1  -3  5] 3  6  7  → 5
         1  3  -1 [-3  5  3] 6  7  → 5
         1  3  -1  -3 [5  3  6] 7  → 6
         1  3  -1  -3  5 [3  6  7] → 7
output = [3, 3, 5, 5, 6, 7]

Пример 2

nums = [1], k = 1
output = [1]

Подсказка

Полный перебор — O(n·k). Храните индексы в деке так, чтобы значения при них шли по убыванию: тогда максимум окна всегда в начале дека, а «бесполезные» меньшие элементы можно выбрасывать с хвоста.

Решение

from collections import deque

def max_sliding_window(nums, k):
    dq, answer = deque(), []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:      # вышел из окна
            dq.popleft()
        while dq and nums[dq[-1]] < x:    # заведомо не станет максимумом
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            answer.append(nums[dq[0]])    # head — максимум окна
    return answer

Сложность: время O(n) (каждый индекс попадает в дек и покидает его не более одного раза), память O(k).