Medium

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= nums.length <= 10^5
  • nums[i] 不是 0 就是 1

解题思路

这道题的关键思路是将问题转化为前缀和问题。我们可以将数组中的 0 视为 -1，这样当子数组中 0 和 1 的数量相等时，该子数组的和就为 0。

核心思路：

  1. 将问题转化：遇到 1 时计数器 +1，遇到 0 时计数器 -1
  2. 使用哈希表记录每个前缀和第一次出现的位置
  3. 当某个前缀和再次出现时，说明从上次出现的位置到当前位置之间的子数组和为 0，即 0 和 1 的数量相等

算法步骤：

  • 使用计数器 count 记录当前的"平衡值"（1的个数减去0的个数）
  • 用哈希表存储每个 count 值第一次出现的下标
  • 当遇到相同的 count 值时，计算当前子数组长度并更新最大长度
  • 初始化哈希表时要加入 (0, -1)，表示空前缀的情况

这种方法时间复杂度为 O(n)，空间复杂度为 O(n)，是最优解法。

代码实现

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> mp;
        mp[0] = -1; // 初始化，表示空前缀
        int count = 0;
        int maxLen = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            count += (nums[i] == 1) ? 1 : -1;
            
            if (mp.find(count) != mp.end()) {
                maxLen = max(maxLen, i - mp[count]);
            } else {
                mp[count] = i;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        mp = {0: -1}  # 初始化，表示空前缀
        count = 0
        max_len = 0
        
        for i, num in enumerate(nums):
            count += 1 if num == 1 else -1
            
            if count in mp:
                max_len = max(max_len, i - mp[count])
            else:
                mp[count] = i
        
        return max_len

public class Solution {
    public int FindMaxLength(int[] nums) {
        Dictionary<int, int> mp = new Dictionary<int, int>();
        mp[0] = -1; // 初始化，表示空前缀
        int count = 0;
        int maxLen = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            count += (nums[i] == 1) ? 1 : -1;
            
            if (mp.ContainsKey(count)) {
                maxLen = Math.Max(maxLen, i - mp[count]);
            } else {
                mp[count] = i;
            }
        }
        
        return maxLen;
    }
}

var findMaxLength = function(nums) {
    const mp = new Map();
    mp.set(0, -1); // 初始化，表示空前缀
    let count = 0;
    let maxLen = 0;
    
    for (let i = 0; i < nums.length; i++) {
        count += (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历数组一次，哈希表操作为O(1)
空间复杂度O(n)哈希表最多存储n个不同的前缀和

相关题目