525. Contiguous Array

Stanislav Gumeniuk включен в leetcode leetcode-problem

2020.05.26 226 слов Пару мгновений

Содержание

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

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

пример 1

1
2
3


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

пример 2

1
2
3


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

Идея такая:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


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
}