525

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | 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 } } 请我喝瓶饮料