0525. Contiguous Array ====================== 题目信息 -------- :题号: 0525 :难度: Medium :主题: 二进制数组、连续子数组、零一等量、最大长度 :原题: `LeetCode 0525 `_ :重点: 子数组必须连续、0 和 1 的数量必须完全相等、返回最大长度而不是区间本身 题目重述 -------- 给定一个只包含 ``0`` 和 ``1`` 的数组 ``nums``,寻找其中最长的连续子数组,使该子数组内 ``0`` 的数量与 ``1`` 的数量相等,并返回其长度。 若不存在非空的合格子数组,返回 ``0``。相同数量要求子数组长度必为偶数;不能跳过中间元素,也不需要返回具体起止下标。 自建示例 -------- 存在多个同长度最长区间: .. code-block:: text 输入:nums = [0,1,1,0,1,0,0] 输出:6 解释:下标 0..5 和 1..6 的连续子数组都各含 3 个 0 与 3 个 1,长度为 6。 没有等量区间: .. code-block:: text 输入:nums = [1,1,1] 输出:0 解释:任意非空连续子数组都不含 0。 把 0 和 1 转为相反的余额 ------------------------ 扫描数组时把 ``1`` 记为 ``+1``、``0`` 记为 ``-1``。若两个前缀在同一位置得到相同余额,它们之间的区间净余额为 0,意味着其中 0 和 1 数量相等。记录每个余额最早出现的下标,重复时用当前位置减最早位置更新最大长度。 前缀余额 0 的初始位置设为 ``-1``,保证从数组开头开始的合法区间也能计入。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int findMaxLength(std::vector& nums) { std::unordered_map first; first[0] = -1; int balance = 0; int answer = 0; for (int i = 0; i < static_cast(nums.size()); ++i) { balance += nums[i] == 1 ? 1 : -1; auto it = first.find(balance); if (it == first.end()) { first[balance] = i; } else { answer = std::max(answer, i - it->second); } } return answer; } }; 代码分析 -------- 相同余额的两个前缀之间恰好抵消了 0 和 1 的贡献,最早位置策略使同一终点得到最长区间。时间复杂度为 ``O(n)`` 平均,额外空间复杂度为 ``O(n)``。