连续数组

[louzhedong]

习题

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1

思路

和上一题一样，采用前缀和+map

解答

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function(nums) {
    var ans = 0;
    var map = {0: -1}
    var sum = 0;
    for (var i = 0; i < nums.length; i++) {
        if (nums[i]) {
            sum++;
        } else {
            sum--;
        }
        if (map[sum] != undefined) {
            ans = Math.max(ans, i - map[sum]);
        } else {
            map[sum] = i;
        }
    }
    return ans;
};

go

func findMaxLength(nums []int) int {
    length := len(nums)
    ans := 0
    _map := make(map[int]int)
    _map[0] = -1
    sum := 0
    for i := 0; i < length; i++ {
        if nums[i] == 1 {
            sum++
        } else {
            sum--
        }
        value, ok := _map[sum]
        if ok {
            current := i - value
            if current > ans {
                ans = current
            }
        } else {
            _map[sum] = i
        }
    }
    return ans
}