M3719.最长平衡子数组 I

hash table, https://leetcode.cn/problems/longest-balanced-subarray-i/)

给你一个整数数组 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^5

这个问题可以通过双重循环枚举子数组的方法来解决。

解题思路

1. 题目定义：一个子数组是“平衡的”，当且仅当该子数组中不同偶数的数量等于不同奇数的数量。
2. 数据规模：数组长度 $n\le 1500$。这意味着 $O(n^2)$ 的算法时间复杂度大约为 ${1500}^2=2.25\times {10}^6$，在 Python 的执行时限内（通常为 ${10}^8$ 次操作/秒）是可以接受的。
3. 算法流程：
   • 遍历每一个可能的子数组起点 $i$。
   • 固定起点 $i$，向右移动终点 $j$。
   • 在移动 $j$ 的过程中，使用两个集合 (Set) 分别记录当前子数组 nums[i...j] 中出现的不同偶数和不同奇数。
   • 每次添加一个新元素后，比较两个集合的大小：如果 len(even_set) == len(odd_set)，则更新最长长度。

Python 代码实现

from typing import List

class Solution:
    def longestBalanced(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = 0
        
        # 遍历子数组的起始位置
        for i in range(n):
            evens = set()
            odds = set()
            # 遍历子数组的结束位置
            for j in range(i, n):
                num = nums[j]
                if num % 2 == 0:
                    evens.add(num)
                else:
                    odds.add(num)
                
                # 判断不同偶数数量是否等于不同奇数数量
                if len(evens) == len(odds):
                    # 更新最长平衡子数组的长度
                    current_len = j - i + 1
                    if current_len > max_len:
                        max_len = current_len
                        
        return max_len

复杂度分析

• 时间复杂度：$O(n^2)$。外层循环执行 $n$ 次，内层循环平均执行 $n/2$ 次。在内层循环中，集合的添加和长度获取操作的时间复杂度均为 $O(1)$。对于 $n=1500$，计算量约为 ${10}^6$ 级，符合要求。
• 空间复杂度：$O(n)$。在内层循环中，集合最多存储 $n$ 个不同的元素。