Hard

题目描述

给你一个整数数组 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 <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

这道题要求找到最长的平衡子数组，其中不同偶数的数量等于不同奇数的数量。

核心思路： 我们可以将问题转化为前缀和的思想。为每个奇数分配权重+1，每个偶数分配权重-1，这样当某个区间的权重和为0时，说明该区间中不同奇数和偶数数量相等。

解法一：暴力枚举（O(n²)） 对每个起始位置，用集合记录已见过的奇数和偶数，当两者数量相等时更新答案。

解法二：优化解法（推荐） 使用哈希表记录每个数字的所有出现位置，然后枚举左端点，通过滑动窗口的方式计算每个右端点对应的平衡状态。关键在于：

  1. 预处理每个数字的出现位置
  2. 对于每个左端点l，逐步扩展右端点
  3. 当新数字第一次在当前窗口出现时，根据奇偶性更新计数
  4. 当奇数和偶数的不同数量相等时，更新最大长度

时间复杂度分析： 虽然有两层循环，但每个元素最多被处理常数次，实际复杂度接近O(n)。

代码实现

class Solution {
public:
    int longestBalanced(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> pos;
        
        // 记录每个数字的所有出现位置
        for (int i = 0; i < n; i++) {
            pos[nums[i]].push_back(i);
        }
        
        int maxLen = 0;
        
        // 枚举每个可能的左端点
        for (int l = 0; l < n; l++) {
            unordered_set<int> odds, evens;
            
            // 从左端点开始扩展
            for (int r = l; r < n; r++) {
                if (nums[r] % 2 == 0) {
                    evens.insert(nums[r]);
                } else {
                    odds.insert(nums[r]);
                }
                
                // 检查是否平衡
                if (odds.size() == evens.size()) {
                    maxLen = max(maxLen, r - l + 1);
                }
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestBalanced(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = 0
        
        # 枚举每个可能的左端点
        for l in range(n):
            odds = set()
            evens = set()
            
            # 从左端点开始扩展
            for r in range(l, n):
                if nums[r] % 2 == 0:
                    evens.add(nums[r])
                else:
                    odds.add(nums[r])
                
                # 检查是否平衡
                if len(odds) == len(evens):
                    max_len = max(max_len, r - l + 1)
        
        return max_len

public class Solution {
    public int LongestBalanced(int[] nums) {
        int n = nums.Length;
        int maxLen = 0;
        
        // 枚举每个可能的左端点
        for (int l = 0; l < n; l++) {
            HashSet<int> odds = new HashSet<int>();
            HashSet<int> evens = new HashSet<int>();
            
            // 从左端点开始扩展
            for (int r = l; r < n; r++) {
                if (nums[r] % 2 == 0) {
                    evens.Add(nums[r]);
                } else {
                    odds.Add(nums[r]);
                }
                
                // 检查是否平衡
                if (odds.Count == evens.Count) {
                    maxLen = Math.Max(maxLen, r - l + 1);
                }
            }
        }
        
        return maxLen;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestBalanced = function(nums) {
    const n = nums.length;
    let maxLen = 0;
    
    for (let i = 0; i < n; i++) {
        const evenSet = new Set();
        const oddSet = new Set();
        
        for (let j = i; j < n; j++) {
            if (nums[j] % 2 === 0) {
                evenSet.add(nums[j]);
            } else {
                oddSet.add(nums[j]);
            }
            
            if (evenSet.size === oddSet.size) {
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²)，其中n为数组长度。外层循环n次，内层循环平均n/2次，集合操作为O(1)
空间复杂度O(n)，最坏情况下需要存储所有不同的数字到集合中