| 6 | |
| 7 | impl Solution { |
| 8 | pub fn find_max_length(nums: Vec<i32>) -> i32 { |
| 9 | if nums.is_empty() { return 0 } |
| 10 | let mut sum = 0; |
| 11 | let mut height = Vec::with_capacity(nums.len() + 1); |
| 12 | let mut map: Vec<(usize, usize)> = Vec::with_capacity(nums.len() * 2 + 1); |
| 13 | for _ in 0..map.capacity() { |
| 14 | map.push((usize::max_value(), usize::max_value())); |
| 15 | } |
| 16 | height.push(0); |
| 17 | let base = nums.len(); |
| 18 | map[base + 0].0 = 0; |
| 19 | |
| 20 | // O (n) |
| 21 | for i in 0..nums.len() { |
| 22 | sum += if nums[i] == 0 { -1 } else { 1 }; |
| 23 | height.push(sum); |
| 24 | let idx: usize = (base as i32 + sum) as usize; |
| 25 | if map[idx].0 == usize::max_value() { |
| 26 | map[idx].0 = i + 1; |
| 27 | } else { |
| 28 | map[idx].1 = i + 1; |
| 29 | } |
| 30 | } |
| 31 | let mut res = 0; |
| 32 | |
| 33 | // O (2n+1) |
| 34 | for i in 0..map.len() { |
| 35 | if map[i].1 != usize::max_value() && map[i].1 - map[i].0 > res { |
| 36 | res = map[i].1 - map[i].0; |
| 37 | } |
| 38 | } |
| 39 | res as i32 |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | #[cfg(test)] |