未排序数组中累加和为给定值的最长子数组系列问题补2

[编程题]未排序数组中累加和为给定值的最长子数组系列问题补2

热度指数：2145 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无序数组arr，其中元素只能是1或0。求arr所有的子数组中0和1个数相等的最长子数组的长度

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行一个整数N，表示数组长度
接下来一行有N个数表示数组中的数

输出描述:

输出一个整数表示答案

示例1

输入

5
1 0 1 0 1

输出

备注:

算法知识视频讲解

Python

湉子1131

N = int(input())
nums = list(map(int,input().split()))

sums = 0
dic = {0:-1}
ans = 0

for i in range(N):
    if nums[i]==1:
        sums += 1
    else:
        sums -= 1
    if sums not in dic:
        dic[sums] = i
    else:
        ans = max(ans,i-dic[sums])
print(ans)

发表于 2019-10-08 20:38:00 回复(0)