题目描述：

LeetCode 525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.

题目大意：

给定一个二进制数组，求其中满足0的个数与1的个数相等的最长子数组

注意：给定二进制数组的长度不超过50,000

解题思路：

动态规划（Dynamic Programming）

时间复杂度 O(n)，n为数组nums的长度

首先，将原始数组nums中的0替换为-1

预处理出数组sums，记录数组nums的前i项和；sums[i] - sums[j - 1]即为nums[j .. i]的和

然后利用数组dmap，记录前i项和的最大下标

遍历数组sums，记当前下标为i，令m = sums[i]：

  如果m == 0，则ans = max(ans, i + 1)
  
  否则，ans = max(ans, dmap[m] - i)

Python代码：

class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sums = [0] * len(nums)
        dmap = collections.defaultdict(int)
        last = 0
        for i, n in enumerate(nums):
            last += 2 * nums[i] - 1
            sums[i] = last
            dmap[last] = max(dmap[last], i)
        ans = 0
        for i, m in enumerate(sums):
            if m == 0:
                ans = max(ans, i + 1)
            else:
                ans = max(ans, dmap[m] - i)
        return ans

上述代码可以精简为一趟遍历，sums数组可以省去，dmap数组记录前i项和的最小下标。

Python代码：

class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dmap = {0 : -1}
        ans = total = 0
        for i, n in enumerate(nums):
            total += 2 * nums[i] - 1
            if total in dmap:
                ans = max(ans, i - dmap[total])
            else:
                dmap[total] = i
        return ans

 

本文链接：http://bookshadow.com/weblog/2017/02/19/leetcode-contiguous-array/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码