难度: Medium
原题连接
内容描述
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.
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
前缀和与后缀和，超时
class Solution:
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
prefix = [0] * (len(nums) + 1)
suffix = [0] * (len(nums) + 1)
sums = sum(nums)
for i in range(1, len(nums)+1):
prefix[i] = prefix[i-1] + nums[i-1]
for i in range(1, len(nums)+1):
suffix[i] = suffix[i-1] + nums[len(nums)-i]
res = 0
for i in range(len(nums)+1):
for j in range(len(nums) - i + 1):
tmp = sums - suffix[j] - prefix[i]
if (len(nums) - i - j) % 2 == 0 and tmp == (len(nums) - i - j) // 2:
res = max(res, (len(nums) - i - j))
return res
思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
segment tree, 超时
import math
class SegmentTree(object):
def __init__(self, nums):
self.nums = nums
self.range_len = len(nums)
power = math.ceil(math.log(self.range_len, 2)) if self.range_len else 0
self.st = [0] * (2 ** (power + 1))
self.constrcut(nums, 0, self.range_len - 1, 0)
# A utility function to get the middle index from corner indexes.
def getMid(self, start, end):
return start + (end - start) // 2
# A recursive function that constructs Segment Tree for array[start..end].
# cur is the index of current node in segment tree self.st
# Time Complexity for tree construction is O(n).
# There are total 2n-1 nodes, and value of every node is calculated only once in tree construction.
def constrcut(self, nums, start, end, cur): # O(N)
if start > end:
return
if start == end:
self.st[cur] = nums[start]
return nums[start]
mid = self.getMid(start, end)
self.st[cur] = self.constrcut(nums, start, mid, 2 * cur + 1) + \
self.constrcut(nums, mid + 1, end, 2 * cur + 2)
return self.st[cur]
def getSumHelper(self, start, end, query_start, query_end, cur):
if query_start <= start and query_end >= end:
return self.st[cur]
if end < query_start or start > query_end:
return 0
mid = self.getMid(start, end)
return self.getSumHelper(start, mid, query_start, query_end, 2 * cur + 1) + \
self.getSumHelper(mid + 1, end, query_start, query_end, 2 * cur + 2)
# Time complexity to query is O(Logn).
# To query a sum, we process at most four nodes at every level and number of levels is O(Logn).
def getSum(self, query_start, query_end):
if query_start < 0 or query_end > self.range_len - 1 or query_start > query_end:
# print('Invalid Input')
return -1
return self.getSumHelper(0, self.range_len - 1, query_start, query_end, 0)
# idx --> index of the element to be updated. This index is in input nums.
def updateValueHelper(self, start, end, idx, diff, cur):
if idx < start or idx > end:
return
self.st[cur] += diff
if end != start:
mid = self.getMid(start, end)
self.updateValueHelper(start, mid, idx, diff, 2 * cur + 1)
self.updateValueHelper(mid + 1, end, idx, diff, 2 * cur + 2)
# The time complexity of update is also O(Logn).
# To update a leaf value, we process one node at every level and number of levels is O(Logn).
def updateValue(self, idx, new_val): # O(lgN)
if idx < 0 or idx > self.range_len - 1:
# print('Invalid Input')
return
diff = new_val - self.nums[idx]
self.nums[idx] = new_val
self.updateValueHelper(0, self.range_len - 1, idx, diff, 0)
class Solution:
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
s = SegmentTree(nums)
res = 0
for i in range(len(nums)):
for j in range(len(nums)):
tmp = s.getSum(i, j)
if (j - i + 1) % 2 == 0 and tmp == (j - i + 1) // 2:
res = max(res, (j - i + 1))
return res
思路 3 - 时间复杂度: O(N)- 空间复杂度: O(N)******
一次遍历，我们用个cnt来记录当前一共碰到了几个1，即碰到1的话cnt就加1，碰到0的话cnt就减1
然后再搞一个字典记录第一次出现某一个cnt值所对应的index值，比如我们第一次碰到了cnt = 2的时候是在index为7的时候，然后在index为16的时候cnt又等于2了， 那肯定说明在index 8到16的这个区间中1和0的数量相等，就更新一下我们的res
比如最开始的时候，cnt为0，第一次碰到cnt为0的情况我们还没有开始遍历呢，此时index自然为-1
beats 31.12%
class Solution:
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res, cnt, lookup = 0, 0, {0: -1}
for i, num in enumerate(nums):
if num == 1:
cnt += 1
else:
cnt -= 1
if cnt in lookup:
res = max(res, i - lookup[cnt])
else:
lookup[cnt] = i
return res