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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | 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} |
评论 (0)
