Day50: 连续数组

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组(的长度)。

示例 1:

输入: [0,1]

输出: 2

说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

示例 2:

输入: [0,1,0]

输出: 2

说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

注意: 给定的二进制数组的长度不会超过50000。

补充下面代码

class Solution(object):

   # def findMaxLength(self, nums):
          # pass

来源: https://leetcode-cn.com/problems/contiguous-array/

class Solution(object):
def findMaxLength(self, nums):
max_len = 0
for index, num in enumerate(nums):
if num == 0:
nums[index] = -1

    # 暴力法
    if len(nums) <2 :return 0 # 仅零或一个元素,返回0
    for i in range(len(nums)):
        for j in range(1, len(nums)+1):
            if sum(nums[i:j+1]) ==0:
                if j-i > max_len:
                    max_len = j-i+1
    return max_len

def findMaxLength1(self, nums):
    max_len , count = 0, 0
    d = {0:-1}
    for index, num in enumerate(nums):
        if num == 0:
            count += -1
        if num ==1:
            count += 1
        if count in d:
            max_len = max(max_len, index - d[count])
        else:
            d[count] = index
    return max_len

def test_findMaxLength():
s = Solution()
nums = [0,1]
assert s.findMaxLength(nums) == 2
nums = [0,1,0]
assert s.findMaxLength(nums) == 2
nums = [0,1,0,1,0,1]
assert s.findMaxLength(nums) == 6
nums = [0,1,0,1,0,1, 1]
assert s.findMaxLength(nums) == 6
nums = [0,1,0,1,0,1,1,1,1,1,0,0,0,0,0]
assert s.findMaxLength(nums) == 14
nums = [1,1,1,1,1,1,1,1]
assert s.findMaxLength(nums) == 0

nums = [0,1]
assert s.findMaxLength1(nums) == 2
nums = [0,1,0]
assert s.findMaxLength1(nums) == 2
nums = [0,1,0,1,0,1]
assert s.findMaxLength1(nums) == 6
nums = [0,1,0,1,0,1, 1]
assert s.findMaxLength1(nums) == 6
nums = [0,1,0,1,0,1,1,1,1,1,0,0,0,0,0]
assert s.findMaxLength1(nums) == 14
nums = [1,1,1,1,1,1,1,1]
assert s.findMaxLength1(nums) == 0
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容