This is the third day of my participation in the Gwen Challenge

Problem description

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Given a binary array nums, find the longest continuous subarray with the same number of 0s and 1s, and return the length of that subarray.

Example 1:

Input: nums = [0,1] Output: 2 Explanation: [0,1] is the longest subarray with an equal number of 0 and 1.Copy the code

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Copy the code

Constraints:


  • 1 1
    Or less \le     nums.length
    Or less \le
    1 0 5 10 ^ 5
  • nums[i] is either
    0 0     or
    1 1

Tip:


  • 1 1
    Or less \le     nums.length
    Or less \le
    1 0 5 10 ^ 5
  • nums[i]not
    0 0     is
    1 1

Their thinking

The key rule is that if the answer is not zero, the subarray must be even in length and at least 2

Use prefixes and hash tables

Specifically, nums[I] values of 0 are treated as −1 when preprocessing prefixes and.

Thus, the problem is transformed into: how to find the longest interval and the subarray of 0.

Also use a hash table to record what the minimum subscript for a certain prefix and occurrence is.

Combined with the “if the answer is non-zero, the subarray length is at least 2” feature, we let the loop start at 2 and go to the “hash table” at the beginning of the loop to store the sentinel, thus eliminating the need to deal with bounds.

code

Python code

class Solution:
    def findMaxLength(self, nums: List[int]) - >int:
        Record the array length
        n = len(nums)
        Initialize the prefix and list
        sum_list = [0] * (n + 1)
        for i in range(1, n + 1) :# record prefix and
            sum_list[i] = sum_list[i - 1] + (1 if nums[i - 1] = =1 else -1)
        ans = 0
        Save using a hash table (dictionary)
        hashmap = {0: 0}
        for i in range(2, n + 1) :if sum_list[i - 2] not in hashmap:
                hashmap[sum_list[i - 2]] = i - 2
            if sum_list[i] in hashmap:
                ans = max(ans, i - hashmap[sum_list[i]])
        return ans

Copy the code

C + + code

class Solution:
    def findMaxLength(self, nums: List[int]) -> intRecord array length n = lenSum_list = [0] * (n + 1)
        for i in range(1, n + 1Sum_list [I] = sum_list[I -1] + (1 if nums[i - 1] = =1 else - 1)
        ans = 0Use hash table (dictionary) to save hashmap = {0: 0}
        for i in range(2, n + 1) :if sum_list[i - 2] not in hashmap:
                hashmap[sum_list[i - 2]] = i - 2
            if sum_list[i] in hashmap:
                ans = max(ans, i - hashmap[sum_list[i]])
        return ans
Copy the code