Ctrl K

Самое широкое окно с равным счётом

Средняя
Два датчика каждую минуту отмечают, сработали они (1) или нет (0). Их журналы — массивы first и second одинаковой длины. Найдите самое длинное окно подряд идущих минут [i, j] (i ≤ j), за которое датчики сработали одинаковое число раз, то есть сумма first[i..j] равна сумме second[i..j]. Верните длину этого окна j - i + 1, а если такого окна нет — 0.
Пример 1
first=[1, 0, 1, 1, 0], second=[0, 1, 1, 0, 0] → 4

Окно с индексами 0–3: в first единиц 1 + 0 + 1 + 1 = 3, в second — 0 + 1 + 1 + 0 = 2, не подходит. А окно 1–4: 0 + 1 + 1 + 0 = 2 и 1 + 1 + 0 + 0 = 2 — равны, длина 4. Всё окно 0–4 даёт 3 против 2.

Пример 2
first=[1, 1], second=[0, 0] → 0

В любом окне в first единиц больше, чем в second, — ответ 0.

Пример 3
first=[0, 1, 0], second=[1, 0, 1] → 2
Ограничения
  • 1 ≤ n ≤ 10⁵, где n = len(first) = len(second)
  • first[i] и second[i] равны 0 или 1
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамый длинный отрезок с заданной суммой СредняяОтрезок с суммой, кратной делителю СредняяПоровну орлов и решек СредняяОтрезки с заданной суммой СредняяОкна с заданным числом тревог Средняя
загружаем Python…
Вход
first=[1, 0, 1, 1, 0], second=[0, 1, 1, 0, 0]
Ожидается
4

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 82 теста на сервере, включая скрытые.