算法题 leecode 525.连续数组

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

题目

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

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

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

解题思路

注意

• 数组中只会有0、1 两种数据
• 相同数量的 0 和 1 的最长连续子数组中肯定包含有相同数量的0和1

这里我们要利用0和1数量相同，互相抵消的特性
如果我们把0都当做-1， 1还是1，沿着数组求和，对于以下数组
[0, 1, 1, 0, 1, 1, 1, 0]

我们可以想到如果2个位置(i, j)之间有相同数量0和1的最长连续数组, 那么这2个位置的sum(i) == sum(j)

这里要注意的是，对于数组初始的sum值是0，我们可以记为sum(-1) = 0
要找到最长连续子数组，只需找到sum值相同，且位置相距最大的情况即可

最终代码

find_max.go

func findMaxLength(nums []int) int {
    // sum -> index
    // 存最小值
    cache := map[int]int{}
    cache[0] = -1
    sum := 0
    res := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            sum -= 1
        } else {
            sum += 1
        }
        if _, ok := cache[sum]; ok {
            index := cache[sum]
            res = max(i-index, res)
        } else {
            cache[sum] = i
        }
    }
    return res
}

func max(a int, b int) int {
    if a < b {
        return b
    } else {
        return a
    }
}

请我喝瓶饮料