Сложность: medium
Дан бинарный массив nums. Верните максимальную длину непрерывного подмассива с равным количеством 0 и 1.
Пример:
Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
👨💻 Алгоритм:
1⃣Инициализируйте переменную count для отслеживания разности между количеством 1 и 0, и переменную max_length для хранения максимальной длины подмассива. Создайте хеш-таблицу map для хранения первых встреч каждого значения count. Добавьте начальное значение (0, -1) в хеш-таблицу.
2⃣Итеративно пройдите по массиву nums. На каждой итерации обновляйте значение count (увеличивайте на 1 для 1 и уменьшайте на 1 для 0). Если текущее значение count уже существует в хеш-таблице, вычислите длину подмассива между текущим индексом и индексом из хеш-таблицы. Обновите max_length, если текущий подмассив длиннее.
3⃣Если текущее значение count не существует в хеш-таблице, добавьте его с текущим индексом. После завершения итерации верните max_length.
😎 Решение:
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
count_map = {0: -1}
max_length = 0
count = 0
for i, num in enumerate(nums):
count += 1 if num == 1 else -1
if count in count_map:
max_length = max(max_length, i - count_map[count])
else:
count_map[count] = i
return max_length
Ставь 👍 и забирай 📚 Базу знаний