给定一个二进制数组, 找到含有相同数量的 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
网友评论