Medium

题目描述

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

提示：

  • 使用暴力法
  • 尝试每个子数组，使用映射/集合数据结构来跟踪不同的偶数和奇数

解题思路

解题思路

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

暴力枚举法（推荐）

由于数组长度最大为1500，我们可以使用暴力方法枚举所有可能的子数组：

  1. 双重循环：外层循环确定起始位置，内层循环确定结束位置
  2. 实时维护：在扩展子数组的过程中，使用两个集合分别记录当前子数组中的不同偶数和奇数
  3. 判断平衡：每次扩展后检查两个集合的大小是否相等，如果相等则更新最大长度
  4. 奇偶判断：通过 num % 2 来判断数字的奇偶性

这种方法的优势在于：

  • 逻辑清晰，易于理解和实现
  • 在扩展子数组时实时维护状态，避免重复计算
  • 时间复杂度虽然是O(n²)，但在题目给定的数据范围内完全可行

优化思路

虽然暴力法已经足够，但也可以考虑其他优化方向：

  • 使用哈希表记录状态差值，但由于需要区分不同数字，实现复杂度较高
  • 分治法理论可行，但对于此题意义不大

综合考虑，暴力枚举法是最直观且高效的解决方案。

代码实现

class Solution {
public:
    int longestBalanced(vector<int>& nums) {
        int n = nums.size();
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            unordered_set<int> evens, odds;
            for (int j = i; j < n; j++) {
                if (nums[j] % 2 == 0) {
                    evens.insert(nums[j]);
                } else {
                    odds.insert(nums[j]);
                }
                
                if (evens.size() == odds.size()) {
                    maxLen = max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestBalanced(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = 0
        
        for i in range(n):
            evens, odds = set(), set()
            for j in range(i, n):
                if nums[j] % 2 == 0:
                    evens.add(nums[j])
                else:
                    odds.add(nums[j])
                
                if len(evens) == len(odds):
                    max_len = max(max_len, j - i + 1)
        
        return max_len

public class Solution {
    public int LongestBalanced(int[] nums) {
        int n = nums.Length;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            HashSet<int> evens = new HashSet<int>();
            HashSet<int> odds = new HashSet<int>();
            
            for (int j = i; j < n; j++) {
                if (nums[j] % 2 == 0) {
                    evens.Add(nums[j]);
                } else {
                    odds.Add(nums[j]);
                }
                
                if (evens.Count == odds.Count) {
                    maxLen = Math.Max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
}

var longestBalanced = function(nums) {
    let maxLen = 0;
    
    for (let i = 0; i < nums.length; i++) {
        let evenSet = new Set();
        let oddSet = new Set();
        
        for (let j = i; j < nums.length; 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²)
空间复杂度O(n)

时间复杂度说明： 双重循环遍历所有子数组，外层循环O(n)，内层循环O(n)，集合操作平均O(1)。

空间复杂度说明： 使用两个集合存储不同的偶数和奇数，最坏情况下存储所有元素，空间复杂度为O(n)。