Задача: 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.

😎 Решение:

using System.Collections.Generic;

public class Solution {
    public int FindMaxLength(int[] nums) {
        Dictionary<int, int> countMap = new Dictionary<int, int> { {0, -1} };
        int maxLength = 0;
        int count = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            count += (nums[i] == 1 ? 1 : -1);
            
            if (countMap.ContainsKey(count)) {
                maxLength = Math.Max(maxLength, i - countMap[count]);
            } else {
                countMap[count] = i;
            }
        }
        
        return maxLength;
    }
}

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