Contiguous Array

Средняя№525сумма подмассива

Дан массив из нулей и единиц. Нужно найти длину самого длинного непрерывного подмассива, в котором нулей и единиц поровну. Наш пример: [0, 1, 1, 0, 1, 1, 1, 0, 0] — ответ 6: [0, 1, 1, 1, 0, 0] с индекса 3 по 8.

525 Contiguous ArrayРазбор · 1×

Пример: [0, 1, 1, 0, 1, 1, 1, 0, 0]. Под числами — баланс: +1 за каждую 1 и -1 за каждый 0 до этого места; он стоит перед следующим числом.

numsbalance-10+11+11-10+11+11+11-10-10
ещё не дошлиуже пройденотекущеегде этот баланс был впервыенулей и единиц поровну

Пока ничего не нашли: best = 0

01/36
сначала · назад · пуск · шаг
Скорость
1function findMaxLength(nums):
2 best = 0
3 balance = 0
4 first = map {0: -1} // balance → its first index
5 for i from 0 to len(nums) - 1:
6 if nums[i] == 1: balance = balance + 1
7 else: balance = balance - 1
8 if balance in first:
9 best = max(best, i - first[balance])
10 else:
11 first[balance] = i
12 return best
состояние
best
0
balance
–
first
–
i
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Считаем 1 за +1, а 0 за -1. В отрезке нулей и единиц поровну ровно тогда, когда его сумма 0, то есть когда баланс на двух его концах одинаковый.
  2. Самый длинный отрезок, который кончается на i, начинается сразу после первого индекса с тем же балансом. Поэтому first хранит для баланса только первый индекс и никогда его не перезаписывает: на индексе 4 баланс 1 возвращается, а first[1] остаётся 2.
  3. first начинается с {0: -1} — баланса 0 до индекса 0, поэтому считается и отрезок с самого начала, как здесь [0, 1] и [0, 1, 1, 0].

Сложность

Время O(n): один проход, а поиск и запись в словаре в среднем O(1). Память O(n): баланс лежит между -n и n, у каждого — один первый индекс.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.