leetcode525-- Contiguous Array

leetcode525-- 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.


这个题目的意思是说,有一个数组,里面的数字全部都是0和1, 现在让找出最大的一个连续的子数组,这个子数组中的0和1的数目是一样的,并且是最大的, 然后结果只需要返回这个最大的长度即可。

这个题目和之前做过的子数组问题有些相似,依然可以用前N项和来解决,不过这时候有一个trick,见到0的话,需要需要减1,见到1的话就加1,这样当前N项和如果一样的话,就意味着中间的这一段里面的0和1的数目是相等的。

具体可以这样写


class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        dic = {}
        summ = 0
        ret = 0
        
        for i in range(len(nums)):
            
            
            if nums[i]:
                summ += 1
            else:
                summ -= 1
            
            if summ ==0:
                ret = max(ret, i+1)
            
            if summ in dic:
                ret = max(ret, i-dic[summ])
            else:
                dic[summ] = i
                
        return ret

其中if summ==0的这里如果不加的话,就把dic[0]=-1给初始化里面去变成下面的。


        
        dic = {}
        dic[0] = -1
        
        summ = 0
        ret = 0
        
        for i in range(len(nums)):
            
            
            if nums[i]:
                summ += 1
            else:
                summ -= 1
            
           
            
            if summ in dic:
                ret = max(ret, i-dic[summ])
            else:
                dic[summ] = i
                
        return ret

用python3的话是


class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        summ = 0
        ret = 0
        
        dic = {}  # 用来存储当前N项和的index.方便后面找到和一样的段。
        for i in range(len(nums)):
            if nums[i]:
                summ += 1
            else:
                summ -= 1
                
            if summ == 0:    # 说明这时候从开始到现在这个地方刚好是满足的.
                ret = max(ret, i+1)
            
            if summ in dic:  # 即有两段的前n项和是一样的,那说明中间的这一段的0和1是一样的.
                ret = max(ret, i - dic[summ])
                
            else:
                dic[summ] = i
                
        return ret

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦