LeetCode 3719. 最长平衡子数组 解题详解（Python）
LeetCode 3719. 最长平衡子数组 解题详解（Python）
1. 问题描述
给你一个整数数组nums。如果子数组中不同偶数的数量等于不同奇数的数量，则称该子数组是平衡的。
目标：返回最长平衡子数组的长度。
关键说明：子数组是数组中连续且非空的一段元素序列。
示例解析
示例 1
输入: nums = [2,5,4,3] 输出: 4 解释: 最长平衡子数组是 [2, 5, 4, 3]。 它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [5, 3]，满足平衡条件，长度为 4。示例 2
输入: nums = [3,2,2,5,4] 输出: 5 解释: 最长平衡子数组是 [3, 2, 2, 5, 4]。 它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [3, 5]，满足平衡条件，长度为 5。示例 3
输入: nums = [1,2,3,2] 输出: 3 解释: 最长平衡子数组是 [2, 3, 2]。 它有 1 个不同的偶数 [2] 和 1 个不同的奇数 [3]，满足平衡条件，长度为 3。约束条件
1 ≤ nums.length ≤ 1500
1 ≤ nums[i] ≤ 10⁵
2. 题目解析与关键观察（核心突破点）
本题的核心是找到“连续子数组”中，不同偶数个数 = 不同奇数个数，并求这类子数组的最大长度。解题的关键的在于避开两个常见误区，同时抓住问题的核心特征：
2.1 常见误区
误区1：混淆“不同个数”与“总个数”——题目要求的是「不同偶数」和「不同奇数」的数量相等，而非偶数、奇数的总个数相等（如示例2中，偶数总个数为3，奇数总个数为2，但不同个数均为2，仍满足条件）。
误区2：暴力枚举所有子数组后去重统计——直接枚举所有子数组（O(n²)个），再对每个子数组统计不同奇偶个数（O(n)），总复杂度O(n³)，虽n=1500时O(n³)≈3.375×10⁹，会超时，需优化。
2.2 关键观察（优化依据）
子数组的连续性：平衡子数组必须是连续的，因此可通过“滑动窗口”或“前缀统计”的方式，高效遍历所有可能的连续子数组。
不同奇偶个数的增量特性：遍历数组时，每新增一个元素，仅需判断其奇偶性，并更新对应“不同集合”的大小，无需重复统计整个子数组的不同元素。
复杂度上限：n=1500，O(n²)复杂度（1500²=2.25×10⁶）完全可行，因此可采用“固定左边界，移动右边界”的暴力优化思路，结合增量统计，将复杂度降至O(n²)。
2.3 解题思路确定
基于上述观察，确定最优解题思路：固定左边界，移动右边界，增量统计当前子数组的不同偶数、奇数个数，判断是否平衡，记录最大长度。
核心逻辑：
遍历每个左边界left（0 ≤ left < n），初始化当前子数组的不同偶数集合、不同奇数集合。
移动右边界right（从left开始，到n-1结束），将nums[right]加入对应集合（偶数→偶集合，奇数→奇集合）。
每次加入后，判断两个集合的大小是否相等，若相等，更新最大长度。
继续移动右边界，直至遍历完所有元素，完成所有左边界的枚举。
3. 代码实现（Python，可直接提交，带详细注释）
严格遵循LeetCode Python题解规范，使用指定的class Solution格式，补充实战注释，规避常见坑点，确保代码可直接复制提交AC。
fromtypingimportListclass