版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://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
    }
}

如果我的文章对你有帮助,你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。

微信支付码

anyShare分享到:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.