Решение задачи про поиск наибольшего подмассива из 0 и 1, где сумма их кол-ва равна друг другу

[vadimr]

HashMap занимает гораздо больше памяти, чем количество хранящихся в нём элементов.

[webnikler]

Согласен ,но обычно затраты памяти берут условно при оценке алгоритма ,в данном случае оценка сводится к кол-ву элементов в хешмапе.

[vadimr]

Затраты памяти берут совсем не условно, а в виде конкретной оценки. Для хеш-таблицы затраты памяти будут O(N), где N – максимальное возможное количество ключей, которое он способен хранить (а не то, которое там фактически хранится). Поэтому меньше размера массива в данном случае никак не получится.

[webnikler]

Я подумал ,что Вы имели ввиду какие-то дополнительные расходы на хранение значений ,помимо самих значений в HashMap. А так да ,Вы правы ,оценка происходит из худшего случая ,при котором N - кол-во элементов в массиве ,а не фактическое кол-во пар в хешмапе.

[AndronNSK]

>>В обоих случаях сумма всех нулей = 2

Прикольное заявление)

[webnikler]

Здесь имел ввиду кол-во нулей ,просмотрел этот момент

[GULT]

обоих случаях сумма всех нулей = 2 

Точно сумма нулей == 2 ? А не 0? )))

[Vankir94]

Вы что тут устроили пехотинцы?

[IpGuru]

Отличная статья, как раз хотел начать изучение алгоритмов!!! Начну с нее)

[webnikler]

Удачи в изучении! Сам нахожусь в процессе)

[Alexandroppolus]

Если currentSum равен 0, то можно просто взять i+1, это заведомо больше текущего maxLen

Ну и вспомогательный массив не нужен, преобразовывать 0 к -1 можно в основном цикле, например currentSum += arr[i] || -1;

[webnikler]

Пример ,боюсь ,что не приведу. А необходимость в том ,чтобы научиться проходить алгоритмические секции собеседований. Я хотел привести свою модель рассуждений при решении подобных задач. Не без косяков ,конечно))

[webnikler]

Да ,смысла в этом действительно нет ,тк i + 1 будет всегда наибольшим. Недоглядел ,спасибо)

[velon]

Долго пытался понять формулировку: "суммы их кол-ва равны друг другу", суммы количества какие-то, почему было не написать: "количество нулей и единиц совпадает"?!

Эту формулировку можно даже сократить до "кол-во 0 и 1 равно", если уж на символах начали экономить.

Самой большой трудностью оказалось понять формулировку задачи. Поправьте как-нибудь

[webnikler]

Согласен ,формулировка некорректная. Буду работать над этим в будущем. "Кол-во единиц и нулей совпадает" здесь гораздо понятнее прозвучало бы

[Alexandroppolus]

"подстрока, в которой поровну нулей и единиц", как то так

[webnikler]

отличный вариант! Заслуживает отдельного лайка)

[wataru]

Не очень удачное объяснение. Почему надо искать текущую сумму в хешмапе-то? Вы так и не объяснили. После замены 0 на -1 вы сказали, что надо найти нибольший кусок с суммой ноль. Дальше надо было бы ввести понятие частичных сумм и указать, что сумма на отрезке есть разность двух таких сумм. И чтобы сумма отрезка была 0, у вас должны быть 2 одинаковые частичные суммы. И вот задача свелась к нахождению одинаковых чисел на наибольшем расстоянии друг от друга. Вот тут уже понятно, откуда взялся хешмап - вы просто запоминаете для каждого числа, где оно первый раз встретилось, и для каждого числа берете разницу между текущей позицией и первой как вариант ответа. И вот эта обработка 0 как особого случая тоже понятнее, если сначала ввести частичные суммы (их же n+1, и первая всегда 0).

И вообще, очень часто задачи, где фигурируют суммы на отрезках в массиве, решаются через частичные суммы. Так что их обязательно надо рассказать.

[webnikler]

Да ,спасибо за совет ,Вы правы. Поставил бы лайк ,но достиг лимита уже( Понял ,что впредь нужно тщательнее подходить к объяснению принципов лежащих в основе решения.

[OlegTar]

можно сразу в hasmap запихнуть ключ 0 со значением -1