525. Непрерывный массив (Contiguous Array)

Задание.

Дан двоичный массив nums

Верните максимальную длину непрерывного подмассива с равным числом 0 и 1.

Пример 1.

Входные данные: nums = [0,1]

Результат: 2

Объяснение: [0, 1] наибольший непрерывный подмассив с равным количеством 0 и 1.

Пример 2.

Входные данные: nums = [0,1,0]

Результат: 2

Объяснение: [0, 1] (or [1, 0]) наибольшие непрерывные подмассивы с равным количеством 0 и 1.

Решение.

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int,int> mp; mp[0] = -1;
        int sum = 0, longest_subarray = 0, len = nums.size(), newlen;
        cout << endl;
        cout << "nums { ";
        for(int i = 0; i < len; i++) {
            cout << nums[i] << " ";
        }
        cout << "} " << endl;
        for(int i = 0; i < len; i++) {
            sum += nums[i] == 0 ? - 1 : 1;

            cout << "nums[" << i << "]: " << nums[i] << ", sum: " << sum << ", longest_subarray: " << longest_subarray;

            if(mp.find(sum) == mp.end()) {
                mp[sum] = i;
                cout << ", mp[" << sum << "] = " << mp[sum];
            } else if(longest_subarray < (newlen = i - mp[sum])) {
                longest_subarray = newlen;
                cout << ", newlen = i - mp[" << sum << "] = " << i << " - " << mp[sum] << " = " << newlen;
            }

            cout << endl;
        }
        return longest_subarray;
    }
};

Способ решения.

При прохождении по массиву nums, вычисляется сумма sum, причём при появлении единицы – сумма увеличивается, при появлении нуля – уменьшается.

Таким образом, если sum == 0, значит количество единиц последовательности равно количеству нулей.

Также в карте mp запоминается индекс первой sum. Когда в следующий раз в последовательности встретится аналогичный sum, это означает, что количество нулей и единиц – одинаковое по сревнению с предыдущей позицией для данного sum.

В этот момент можно произвести обновление значения longest_subarray – хранящей значение наибольшей длины последовательности.

Длина последовательности определяется, как разница между текущим индексом i и первым встреченным индексом, для данного sum (запомненным в карте mp)