Leetcode - Contiguous Array

https://leetcode.com/problems/contiguous-array/

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.

This problem is very similar to this one

1. Convert 0 to -1

2. Find longest sub array with sum 0

And this problem is converted to this one

func findMaxLength(nums []int) int {
    for i := 0; i < len(nums); i++ {
        if nums[i] == 0 {
            nums[i] = -1
        }
    }
    hash := map[int]int{}
    sum := 0
    result := 0
    for i := 0; i < len(nums); i++ {
        sum += nums[i]
        if sum == 0 {
            result = i + 1
        } else {
            if val, ok := hash[sum]; ok {
                result = max(result, i - val)
            }
        }
        if _, ok := hash[sum]; !ok {
            hash[sum] = i
        }
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    
    return b
}

• 相关文章
• 全局相关文章