Задача: 525. Contiguous Array

Сложность: 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.

😎 Решение:

var findMaxLength = function(nums) {
    let countMap = new Map();
    countMap.set(0, -1);
    let maxLength = 0;
    let count = 0;
    
    for (let i = 0; i < nums.length; i++) {
        count += (nums[i] === 1 ? 1 : -1);
        
        if (countMap.has(count)) {
            maxLength = Math.max(maxLength, i - countMap.get(count));
        } else {
            countMap.set(count, i);
        }
    }
    
    return maxLength;
};

Ставь 👍 и забирай 📚 Базу знаний