2026-03-11：最长平衡子数组Ⅰ。用go语言，给定一个整数数组 nums。把数组中任意一段连续且非空的元素称为子数组；如果把子数组里的元素

福大大架构师每日一题

发布于 2026-03-31 20:56:03

610

2026-03-11：最长平衡子数组Ⅰ。用go语言，给定一个整数数组 nums。把数组中任意一段连续且非空的元素称为子数组；如果把子数组里的元素去重后，偶数的个数与奇数的个数相等，就把该子数组称为“平衡子数组”。请找出数组中最长的平衡子数组，并返回它的长度。

1 <= nums.length <= 1500。

1 <= nums[i] <= 100000。

输入: nums = [2,5,4,3]。

输出: 4。

解释:

最长平衡子数组是 [2, 5, 4, 3]。

它有 2 个不同的偶数 [2, 4] 和 2 个不同的奇数 [5, 3]。因此，答案是 4 。

题目来自力扣3719。

一、代码执行过程详细拆解

我们以输入 nums = [2, 5, 4, 3] 为例，分步拆解 longestBalanced 函数的执行逻辑：

步骤1：初始化全局最大值

函数首先定义 maxLen = 0，用于记录找到的最长平衡子数组长度，初始值为0。

步骤2：外层循环确定子数组起始位置

外层 for 循环（i 从0到len(nums)-1）遍历数组的每一个位置，作为子数组的起始下标：

• 当 i=0 时，子数组起始于第0个元素（值为2）；
• 当 i=1 时，子数组起始于第1个元素（值为5）；
• 当 i=2 时，子数组起始于第2个元素（值为4）；
• 当 i=3 时，子数组起始于第3个元素（值为3）。

步骤3：内层循环扩展子数组结束位置

对于每一个起始下标 i，内层 for 循环（j 从i到len(nums)-1）遍历数组，作为子数组的结束下标，并实时统计子数组的奇偶特征：

1. 初始化统计容器：每次外层循环（换起始位置）时，都会新建两个空字典：
- • odd：键为子数组中的奇数，值为该奇数出现的次数（仅记录“存在性”，次数无实际意义）；
- • even：键为子数组中的偶数，值为该偶数出现的次数（同理，次数无实际意义）。
2. 遍历并更新统计：内层循环每遍历一个元素 nums[j]：
- • 判断奇偶：通过 nums[j]&1 == 1 判断（按位与1，结果为1则是奇数，0则是偶数）；
- • 更新字典：奇数则在 odd 中记录该数（次数+1），偶数则在 even 中记录该数（次数+1）。
3. 判断是否平衡并更新最大值：每次更新字典后，检查 odd 和 even 的键的数量（即去重后的奇偶数量）是否相等：
- • 若相等：计算当前子数组长度 j-i+1，如果比 maxLen 大，则更新 maxLen；
- • 若不相等：不做处理，继续内层循环。

步骤4：以示例输入具体走一遍逻辑

输入 nums = [2,5,4,3]：

• i=0（起始为2）：
- • j=0（子数组[2]）：even={2:1}，odd={} → len(even)=1，len(odd)=0 → 不平衡；
- • j=1（子数组[2,5]）：even={2:1}，odd={5:1} → len=1:1 → 平衡，maxLen=2；
- • j=2（子数组[2,5,4]）：even={2:1,4:1}，odd={5:1} → len=2:1 → 不平衡；
- • j=3（子数组[2,5,4,3]）：even={2:1,4:1}，odd={5:1,3:1} → len=2:2 → 平衡，maxLen=4；
• i=1（起始为5）：
- • j=1（[5]）：odd={5:1}，even={} → 不平衡；
- • j=2（[5,4]）：odd={5:1}，even={4:1} → 平衡，长度2（小于当前maxLen=4，不更新）；
- • j=3（[5,4,3]）：odd={5:1,3:1}，even={4:1} → 不平衡；
• i=2（起始为4）：
- • j=2（[4]）：even={4:1}，odd={} → 不平衡；
- • j=3（[4,3]）：even={4:1}，odd={3:1} → 平衡，长度2（不更新）；
• i=3（起始为3）：
- • j=3（[3]）：odd={3:1}，even={} → 不平衡；

最终 maxLen=4，函数返回4，与示例输出一致。

二、时间复杂度与空间复杂度分析

1. 时间复杂度

• 外层循环：遍历数组的每个元素作为起始位置，共 n 次（n 为数组长度）；
• 内层循环：对于每个起始位置 i，内层循环最多遍历 n-i 次，总次数为 n + (n-1) + (n-2) + ... + 1 = n*(n+1)/2，即 O(n²)；
• 内层循环的操作（判断奇偶、更新字典、判断长度）均为 O(1) 时间（字典的增/查操作平均时间复杂度为 O(1)）；
• 综上，总的时间复杂度为 O(n²)（n≤1500时，n²=225万，计算量可接受）。

2. 额外空间复杂度

• 每次外层循环会新建两个字典 odd 和 even，字典的最大大小取决于子数组中去重后的奇偶数量：
- • 最坏情况下（子数组包含所有元素，且所有数都不重复），字典的键数量最多为 n（如数组全为不同奇数/偶数）；
- • 但由于每次外层循环结束后，该次循环的字典会被销毁，因此额外空间复杂度为 O(n)（仅需存储当前子数组的奇偶统计字典）。

总结

1. 核心逻辑：通过双层循环枚举所有可能的子数组，实时统计子数组内去重后的奇偶数量，判断是否平衡并更新最长长度；
2. 时间复杂度：O(n²)（n为数组长度），双层循环是主要时间开销；
3. 空间复杂度：O(n)，额外空间主要用于存储当前子数组的奇偶统计字典。

Go完整代码如下：

package main

import (
    "fmt"
)

func longestBalanced(nums []int)int {
    maxLen := 0

    for i := 0; i < len(nums); i++ {
        odd := make(map[int]int)
        even := make(map[int]int)

        for j := i; j < len(nums); j++ {
            if nums[j]&1 == 1 {
                odd[nums[j]]++
            } else {
                even[nums[j]]++
            }

            iflen(odd) == len(even) {
                if j-i+1 > maxLen {
                    maxLen = j - i + 1
                }
            }
        }
    }

    return maxLen
}

func main() {
    nums := []int{2, 5, 4, 3}
    result := longestBalanced(nums)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def longest_balanced(nums):
    max_len = 0
    
    for i in range(len(nums)):
        odd = {}
        even = {}
        
        for j in range(i, len(nums)):
            if nums[j] & 1:  # 判断是否为奇数
                odd[nums[j]] = odd.get(nums[j], 0) + 1
            else:
                even[nums[j]] = even.get(nums[j], 0) + 1
            
            iflen(odd) == len(even):
                if j - i + 1 > max_len:
                    max_len = j - i + 1
    
    return max_len

def main():
    nums = [2, 5, 4, 3]
    result = longest_balanced(nums)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int longestBalanced(vector<int>& nums) {
    int maxLen = 0;

    for (int i = 0; i < nums.size(); i++) {
        unordered_map<int, int> odd;
        unordered_map<int, int> even;

        for (int j = i; j < nums.size(); j++) {
            if (nums[j] & 1) {  // 判断是否为奇数
                odd[nums[j]]++;
            } else {
                even[nums[j]]++;
            }

            if (odd.size() == even.size()) {
                if (j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                }
            }
        }
    }

    return maxLen;
}

int main() {
    vector<int> nums = {2, 5, 4, 3};
    int result = longestBalanced(nums);
    cout << result << endl;
    return0;
}