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

请我喝瓶饮料

微信支付码