525. Contiguous Array

[Tcdian]

525. Contiguous Array

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

Example 1

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

Example 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.

Note

• The length of the given binary array will not exceed 50,000.

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function(nums) {
    let prefix = 0;
    let result = 0;
    const cache = new Map([[prefix, -1]]);
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 1) {
            prefix += 1;
        } else {
            prefix -= 1;
        }
        if (cache.has(prefix)) {
            result = Math.max(result, i - cache.get(prefix));
        } else {
            cache.set(prefix, i);
        }
    }
    return result;
};

• TypeScript Solution

var findMaxLength = function(nums: number[]): number {
    let prefix = 0;
    let result = 0;
    const cache = new Map([[prefix, -1]]);
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 1) {
            prefix += 1;
        } else {
            prefix -= 1;
        }
        if (cache.has(prefix)) {
            result = Math.max(result, i - (cache.get(prefix) as number));
        } else {
            cache.set(prefix, i);
        }
    }
    return result;
};