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

Попалась мне одна интересная задача ,суть которой — найти наибольший отрезок в массиве единиц и нулей ,где суммы их кол-ва равны друг другу. Например ,имеем массив [0, 1, 0, 1, 0]. Длина наибольшего подмассива ,где кол-во нулей равно кол-ву единиц = 4. Под этот критерий подходит подмассив [{0, 1, 0, 1}, 0] ,а так же [0, {1, 0, 1, 0}]. В обоих случаях сумма всех нулей = 2 ,а сумма всех единиц равна тоже 2. Длина такой последовательности = 4 ,и это должно быть ответом.

Сперва можно немного поработать над данными ,чтобы в будущем можно было проще вычислять такие отрезки ,где суммы 1 и 0 равны друг другу. Например ,для отрезка [0, 1, 0, 1] общая сумма значений равна 2 (0 + 1 + 0 + 1). Можно сделать вывод ,что сумма 1 и 0 равна в этом отрезке ,если сумма значений равна половине длины подмассива. Для нашего случая получается ,что (0 + 1 + 0 + 1) = 2 = 4/2 (половина длины подмассива). Но гораздо проще было бы проводить расчеты ,если бы необходимая сумма значений была бы константой ,например 0. В таком случае мы можем заменить все нули на -1 ,и таким образом получим [-1, 1, -1, 1] ,где сумма таких элементов будет равна 0.

На JavaScript это можно сделать следующим образом: arr.map(x => x || -1).

Далее нам потребуется цикл по длине arr:

for (let i = 0; i < arr.length; i++) { ... }

На самом деле мы можем найти наибольшую последовательность за 1 такой цикл. Нам потребуется создать несколько вспомогательных переменных за пределами цикла:

let currentSum — будет хранить текущее значение суммы элементов с 0 по i.

let maxLength — будет хранить промежуточное значение наибольшей длины подмассива ,которую удалось найти на момент i.

const hashMap — временная хешмапа для хранения пар { [currentSum]: [i] }.

currentSum мы на каждой итерации обновляем ,суммируя с элементом текущей итерации:

currentSum += arr[i];

Далее суть решения сводится к тому ,чтобы на каждой итерации цикла проверять наличие currentSum в hashMap ,и если оно там есть ,то вычислить разницу между текущим i и hashMap[currentSum] ,который вернет индекс той позиции ,на которой первый раз было зафиксировано текущее значение currentSum. Иначе записать текущий currentSum в hashMap:

if (currentSum in hashMap) {   maxLength = Math.max(maxLength, i — hashMap[currentSum]); } else {   hashMap[currentSum] = i; }

Здесь мы используем метод Math.max для определения наибольшего из старого значения maxLength и вычисленного нового ,тк не факт ,что новое будет больше.

i - hashMap[currentSum] обозначает длину отрезка ,при котором сумма всех его значений будет равна 0 ,ведь для текущего i currentSum такой же ,как и для индекса извлеченного из hashMap[currentSum] ,а это индекс элемента ,на котором мы впервые получили эту сумму.

Выходит ,что мы по мере итераций копим в хешмапе некоторые уникальные значения сумм и индексы ,на которых они были впервые вычислены ,а затем вычисляем длину отрезка при котором текущая сумма для i и сумма из хешмапы оказались равны.

Не забываем также проверить ,не получилась ли текущая сумма равна 0 ,тогда стоит ее также провалидировать и записать в maxLength при необходимости:

if (currentSum === 0) {   maxLength = Math.max(maxLength, i + 1); }

В конце останется только вывести maxLength. Итоговое решение выглядит так:

function solve(inputArr) {   const arr = inputArr.map(x => x || -1);   const hashMap = {};      let currentSum = 0;   let maxLength = 0;      for (let i = 0; i < arr.length; i++) {     currentSum += arr[i];          if (currentSum === 0) {       maxLength = Math.max(maxLength, i + 1);     }          if (currentSum in hashMap) {       maxLength = Math.max(maxLength, i - hashMap[currentSum]);     } else {       hashMap[currentSum] = i;     }   }      return maxLength; }

Сложность по памяти получается O(n) за счет того ,что мы сделали копию массива ,однако ,если ее не делать ,то будет O(k) ,где k — кол-во пар в hashMap. В худшем случае она будет равна n ,если все элементы последовательности будут одинаковы.

Временная сложность будет равна O(n) ,тк мы целиком проходим циклом по массиву. На самом деле в функции 2 цикла ,тк map тоже является циклом ,но общая сложность сводится к O(n) ,тк константа 2 просто отбросится.