本文共 1438 字，大约阅读时间需要 4 分钟。

原贴地址：

题目

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]输出: 2说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

示例 2:

输入: nums = [0,1,0]输出: 2说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1

思路分析

这道题画张图大家就明白了

每一条线上的任意两点之间，都是一个含有相同数量0和1的连续子数组。

C++代码

class Solution {
   public:    int findMaxLength(vector
   
    & nums) {
           unordered_map
    
      m;        int res = 0;        m[0] = 0;        vector
     
       prefix(nums.size() + 1);        for (int i = 0; i < nums.size(); ++i) {
               prefix[i + 1] = (prefix[i] + nums[i] * 2 - 1);            if (m.find(prefix[i + 1]) != m.end()) {
                   res = max(res, i + 1 - m[prefix[i + 1]]);            } else {
                   m[prefix[i + 1]] = i + 1;             }        }        return res;    }};
     
    
   

Rust代码

use std::collections::HashMap;impl Solution {    pub fn find_max_length(nums: Vec
   
    ) -> i32 {        let mut m = HashMap::new();        let mut res = 0;        m.insert(0, 0);        let mut prefix = vec![0; nums.len() + 1];        for i in 0..nums.len() {            prefix[i + 1] = (prefix[i] + nums[i] * 2 - 1);            if m.contains_key(&prefix[i + 1]) {                res = res.max(i + 1 - m[&prefix[i + 1]]);            } else {                m.insert(prefix[i + 1], i + 1);            }        }        res as i32    }}
   

转载地址：http://kuuci.baihongyu.com/