Условие задачи

Дан бинарный массив, необходимо найти максимальноую длинну непрерывного подмассива с одинаковым количестов нулей и единиц

пример 1

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

пример 2

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Ограничения

• Длинна массива не превышает 50000 элементов.

Решение

Hash map

Идея такая:

1. завести переменную sum
2. идти по массиву и добавлять к сумме 1 если текущий элемент равен 1, и отнимать 1 если текущий элемент равен -1
3. Если по в мапе по ключу текущей суммы есть значение, то сравнить idx-m[sum]+1 и текущий максимум. если максимум меньше - присвоить ему новое значение.
4. Записывать в маппу в ключ значение сумму (если по этому ключу не было значений ранее), а в значение – текущую позицию

func findMaxLength(nums []int) int {
    max := 0
    m := make(map[int]int, 0)
    s:=0
    m[0]=0
    for idx:=range nums {
        if nums[idx] == 1{
            s+=1
        } else {
            s-=1
        }
        _, ok := m[s]
        if ok {
            if idx-m[s]+1>max {
                max = idx-m[s]+1
            }
        } else {
            m[s] = idx+1
        }
        
    }
    
    return max
}