2026-03-13：最长平衡子数组Ⅱ。用go语言，给定一个整数数组 nums。把数组中任意一个连续且非空的区间看作候选段：如果该区间内互不相同的偶数个数与互不相同的奇数个数相同，就称这个区间为“平衡”。请找出所有平衡区间中长度最大的那一个，并输出其长度。

1 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

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

输出: 4。

解释:

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

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

题目来自力扣3721。

一、整体解题思路分步解析

要解决“最长平衡子数组Ⅱ”问题（区间内不同偶数个数 = 不同奇数个数），核心是通过前缀和+懒标记线段树将问题转化为“寻找前缀和为0的最远位置”，以下是详细步骤：

步骤1：定义符号函数，将奇偶性转化为数值

首先定义一个符号函数 sgn(x)：

• 若 x 是偶数，返回 1（代表“新增一个不同偶数”）；
• 若 x 是奇数，返回 -1（代表“新增一个不同奇数”）。
  这个函数的作用是将“统计不同奇偶数量”转化为“数值加减”，后续通过前缀和是否为0来判断“不同偶数数=不同奇数数”。

步骤2：初始化前缀和与位置哈希表

• 前缀和数组 prefixSum：prefixSum[i] 表示从数组第0位到第i位的“符号函数累加值”，初始时 prefixSum[0] = sgn(nums[0])；
• 位置哈希表 occurrences：键是数组元素值，值是该元素出现的所有位置（从1开始计数），初始时将 nums[0] 的位置1存入哈希表。

步骤3：构建初始前缀和数组

遍历数组从第1位到最后一位（索引i）：

1. 先将 prefixSum[i] 初始化为 prefixSum[i-1]（继承前一位的累加值）；
2. 检查哈希表中是否存在当前元素 nums[i] 的记录：
   • 若不存在（说明是该元素第一次出现），则 prefixSum[i] += sgn(nums[i])（新增一个不同奇偶，更新累加值）；
   • 若存在（元素已出现过，不新增不同奇偶），则 prefixSum[i] 保持不变；
3. 将当前元素 nums[i] 的位置 i+1 追加到哈希表对应列表中。
   此时 prefixSum 数组的每个值，代表“从数组开头到当前位置的不同偶数数 - 不同奇数数”。

步骤4：初始化线段树

用构建好的 prefixSum 数组初始化线段树，线段树的每个节点存储：

• minValue：该区间内前缀和的最小值；
• maxValue：该区间内前缀和的最大值；
• lazyTag：懒标记（用于区间批量更新，避免频繁递归）。
  线段树的核心作用是：快速查询“从某个起始位置开始，前缀和等于0的最后一个位置”，以及快速执行“区间加减更新”。

步骤5：遍历数组，动态更新并查找最长平衡区间

遍历数组每个位置i（从0到len(nums)-1），核心目标是找到以i为起点的最长平衡区间：

1. 查找最远平衡位置：调用线段树的 FindLast(i+length, 0) 方法，含义是“从 i+length 位置开始（剪枝优化，避免重复查找），寻找前缀和为0的最后一个位置”，计算该位置与i的差值，更新最大长度 length；
2. 处理当前元素的下一次出现位置：
   • 从哈希表中移除当前元素 nums[i] 的第一个位置（因为i位置的元素已处理，后续区间不再包含它的“首次出现”贡献）；
   • 若哈希表中仍有该元素的位置记录，取第一个位置作为 nextPos（该元素下一次出现的位置）；若没有，nextPos 设为数组长度+1；
3. 区间更新前缀和：调用线段树的 Add(i+1, nextPos-1, -sgn(nums[i])) 方法，含义是“将区间 [i+1, nextPos-1] 内的所有前缀和减去 sgn(nums[i])”。
   这一步的核心逻辑是：当i位置的元素被排除后，后续区间中该元素的“首次出现”贡献会被撤销，因此需要批量更新前缀和（懒标记保证更新效率）。

步骤6：返回最大长度

遍历结束后，length 即为最长平衡子数组的长度。

补充：线段树的核心操作

• build：递归构建线段树，叶子节点存储 prefixSum 对应位置的值，非叶子节点存储区间的min/max；
• pushdown：懒标记下推，将父节点的更新任务传递给子节点（保证区间更新的正确性）；
• pushup：子节点信息向上合并，更新父节点的min/max；
• applyTag：执行区间更新，修改节点的min/max并更新懒标记；
• update：递归执行区间加减操作，利用懒标记减少递归次数；
• find：递归查找“指定区间内前缀和为0的最后一个位置”，优先查找右子树（保证找到“最后一个”），若右子树无结果再查左子树。

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

1. 时间复杂度

• 前缀和构建：遍历数组一次，时间复杂度 O(n)（n为数组长度）；
• 线段树构建：线段树的构建时间为 O(n)（线段树节点数为4n，构建时每个节点处理一次）；
• 遍历更新与查找：
  • 每次 FindLast 操作：线段树的查询时间为 O(logn)（递归深度为树的高度，即 log(4n) ≈ logn）；
  • 每次 Add 操作：线段树的区间更新时间为 O(logn)（懒标记保证单次更新仅需处理 logn 个节点）；
  • 遍历n次，总时间为 O(nlogn)；
• 哈希表操作：哈希表的追加/删除操作均为 O(1) 均摊时间，总时间 O(n)；
• 总时间复杂度：O(nlogn)（n≤1e5时，nlogn 可满足时间要求）。

2. 空间复杂度

• 前缀和数组：占用 O(n) 空间；
• 哈希表：存储每个元素的出现位置，最坏情况下（所有元素不同）占用 O(n) 空间；
• 线段树：节点数为4n，每个节点存储min/max/lazyTag，占用 O(n) 空间；
• 总额外空间复杂度：O(n)（所有辅助空间均为线性级别）。

总结

1. 核心思路：将“统计不同奇偶数量”转化为“前缀和数值计算”，通过线段树快速查找前缀和为0的最远位置，并用懒标记优化区间更新；
2. 关键操作：符号函数转化奇偶性、前缀和记录差值、线段树实现高效查询与更新；
3. 复杂度：时间复杂度 O(nlogn)，空间复杂度 O(n)（n为数组长度）。

Go完整代码如下：

package main

import (
	"fmt"
)

type LazyTag struct {
	toAdd int
}

func (l *LazyTag) Add(other *LazyTag) *LazyTag {
	l.toAdd += other.toAdd
	return l
}

func (l *LazyTag) HasTag() bool {
	return l.toAdd != 0
}

func (l *LazyTag) Clear() {
	l.toAdd = 0
}

type SegmentTreeNode struct {
	minValue int
	maxValue int
	lazyTag  *LazyTag
}

func NewSegmentTreeNode() *SegmentTreeNode {
	return &SegmentTreeNode{
		minValue: 0,
		maxValue: 0,
		lazyTag:  &LazyTag{},
	}
}

type SegmentTree struct {
	n    int
	tree []*SegmentTreeNode
}

func NewSegmentTree(data []int) *SegmentTree {
	n := len(data)
	tree := make([]*SegmentTreeNode, n*4+1)
	for i := range tree {
		tree[i] = NewSegmentTreeNode()
	}
	seg := &SegmentTree{n: n, tree: tree}
	seg.build(data, 1, n, 1)
	return seg
}

func (seg *SegmentTree) Add(l, r, val int) {
	tag := &LazyTag{toAdd: val}
	seg.update(l, r, tag, 1, seg.n, 1)
}

func (seg *SegmentTree) FindLast(start, val int) int {
	if start > seg.n {
		return -1
	}
	return seg.find(start, seg.n, val, 1, seg.n, 1)
}

func (seg *SegmentTree) applyTag(i int, tag *LazyTag) {
	seg.tree[i].minValue += tag.toAdd
	seg.tree[i].maxValue += tag.toAdd
	seg.tree[i].lazyTag.Add(tag)
}

func (seg *SegmentTree) pushdown(i int) {
	if seg.tree[i].lazyTag.HasTag() {
		tag := &LazyTag{toAdd: seg.tree[i].lazyTag.toAdd}
		seg.applyTag(i<<1, tag)
		seg.applyTag((i<<1)|1, tag)
		seg.tree[i].lazyTag.Clear()
	}
}

func (seg *SegmentTree) pushup(i int) {
	left := seg.tree[i<<1]
	right := seg.tree[(i<<1)|1]
	seg.tree[i].minValue = min(left.minValue, right.minValue)
	seg.tree[i].maxValue = max(left.maxValue, right.maxValue)
}

func (seg *SegmentTree) build(data []int, l, r, i int) {
	if l == r {
		seg.tree[i].minValue = data[l-1]
		seg.tree[i].maxValue = data[l-1]
		return
	}

	mid := l + ((r - l) >> 1)
	seg.build(data, l, mid, i<<1)
	seg.build(data, mid+1, r, (i<<1)|1)
	seg.pushup(i)
}

func (seg *SegmentTree) update(targetL, targetR int, tag *LazyTag, l, r, i int) {
	if targetL <= l && r <= targetR {
		seg.applyTag(i, tag)
		return
	}

	seg.pushdown(i)
	mid := l + ((r - l) >> 1)
	if targetL <= mid {
		seg.update(targetL, targetR, tag, l, mid, i<<1)
	}
	if targetR > mid {
		seg.update(targetL, targetR, tag, mid+1, r, (i<<1)|1)
	}
	seg.pushup(i)
}

func (seg *SegmentTree) find(targetL, targetR, val, l, r, i int) int {
	if seg.tree[i].minValue > val || seg.tree[i].maxValue < val {
		return -1
	}

	if l == r {
		return l
	}

	seg.pushdown(i)
	mid := l + ((r - l) >> 1)

	if targetR >= mid+1 {
		res := seg.find(targetL, targetR, val, mid+1, r, (i<<1)|1)
		if res != -1 {
			return res
		}
	}

	if l <= targetR && mid >= targetL {
		return seg.find(targetL, targetR, val, l, mid, i<<1)
	}

	return -1
}

func longestBalanced(nums []int) int {
	occurrences := make(map[int][]int)

	sgn := func(x int) int {
		if x%2 == 0 {
			return 1
		}
		return -1
	}

	length := 0
	prefixSum := make([]int, len(nums))
	prefixSum[0] = sgn(nums[0])
	occurrences[nums[0]] = append(occurrences[nums[0]], 1)

	for i := 1; i < len(nums); i++ {
		prefixSum[i] = prefixSum[i-1]
		occ := occurrences[nums[i]]
		if len(occ) == 0 {
			prefixSum[i] += sgn(nums[i])
		}
		occurrences[nums[i]] = append(occ, i+1)
	}

	seg := NewSegmentTree(prefixSum)
	for i := 0; i < len(nums); i++ {
		length = max(length, seg.FindLast(i+length, 0)-i)
		nextPos := len(nums) + 1
		occurrences[nums[i]] = occurrences[nums[i]][1:]
		if len(occurrences[nums[i]]) > 0 {
			nextPos = occurrences[nums[i]][0]
		}

		seg.Add(i+1, nextPos-1, -sgn(nums[i]))
	}

	return length
}

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

Python完整代码如下：

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

from typing import List, Dict, Optional

class LazyTag:
    """懒标记类，用于延迟更新"""
    def __init__(self, to_add: int = 0):
        self.to_add = to_add
    
    def add(self, other: 'LazyTag') -> 'LazyTag':
        self.to_add += other.to_add
        return self
    
    def has_tag(self) -> bool:
        return self.to_add != 0
    
    def clear(self):
        self.to_add = 0


class SegmentTreeNode:
    """线段树节点"""
    def __init__(self):
        self.min_value = 0
        self.max_value = 0
        self.lazy_tag = LazyTag()


class SegmentTree:
    """线段树实现"""
    def __init__(self, data: List[int]):
        self.n = len(data)
        # Python中可以用列表推导式创建，但为了效率，先创建固定大小的列表
        self.tree = [SegmentTreeNode() for _ in range(self.n * 4 + 1)]
        self._build(data, 1, self.n, 1)
    
    def add(self, l: int, r: int, val: int):
        """区间添加值"""
        tag = LazyTag(to_add=val)
        self._update(l, r, tag, 1, self.n, 1)
    
    def find_last(self, start: int, val: int) -> int:
        """查找最后一个满足条件的位置"""
        if start > self.n:
            return -1
        return self._find(start, self.n, val, 1, self.n, 1)
    
    def _apply_tag(self, i: int, tag: LazyTag):
        """应用懒标记"""
        self.tree[i].min_value += tag.to_add
        self.tree[i].max_value += tag.to_add
        self.tree[i].lazy_tag.add(tag)
    
    def _pushdown(self, i: int):
        """下推懒标记"""
        if self.tree[i].lazy_tag.has_tag():
            tag = LazyTag(to_add=self.tree[i].lazy_tag.to_add)
            self._apply_tag(i << 1, tag)
            self._apply_tag((i << 1) | 1, tag)
            self.tree[i].lazy_tag.clear()
    
    def _pushup(self, i: int):
        """向上更新节点信息"""
        left = self.tree[i << 1]
        right = self.tree[(i << 1) | 1]
        self.tree[i].min_value = min(left.min_value, right.min_value)
        self.tree[i].max_value = max(left.max_value, right.max_value)
    
    def _build(self, data: List[int], l: int, r: int, i: int):
        """构建线段树"""
        if l == r:
            self.tree[i].min_value = data[l - 1]
            self.tree[i].max_value = data[l - 1]
            return
        
        mid = l + ((r - l) >> 1)
        self._build(data, l, mid, i << 1)
        self._build(data, mid + 1, r, (i << 1) | 1)
        self._pushup(i)
    
    def _update(self, target_l: int, target_r: int, tag: LazyTag, l: int, r: int, i: int):
        """更新区间"""
        if target_l <= l and r <= target_r:
            self._apply_tag(i, tag)
            return
        
        self._pushdown(i)
        mid = l + ((r - l) >> 1)
        if target_l <= mid:
            self._update(target_l, target_r, tag, l, mid, i << 1)
        if target_r > mid:
            self._update(target_l, target_r, tag, mid + 1, r, (i << 1) | 1)
        self._pushup(i)
    
    def _find(self, target_l: int, target_r: int, val: int, l: int, r: int, i: int) -> int:
        """查找特定值"""
        if self.tree[i].min_value > val or self.tree[i].max_value < val:
            return -1
        
        if l == r:
            return l
        
        self._pushdown(i)
        mid = l + ((r - l) >> 1)
        
        # 先查找右半部分
        if target_r >= mid + 1:
            res = self._find(target_l, target_r, val, mid + 1, r, (i << 1) | 1)
            if res != -1:
                return res
        
        # 再查找左半部分
        if l <= target_r and mid >= target_l:
            return self._find(target_l, target_r, val, l, mid, i << 1)
        
        return -1


def longest_balanced(nums: List[int]) -> int:
    """
    查找最长平衡子数组的长度
    奇数贡献-1，偶数贡献+1，要求子数组和为0
    """
    # 记录每个数字出现的位置（1-based）
    occurrences: Dict[int, List[int]] = {}
    
    def sgn(x: int) -> int:
        """符号函数：偶数返回1，奇数返回-1"""
        return 1 if x % 2 == 0 else -1
    
    # 计算前缀和
    length = 0
    prefix_sum = [0] * len(nums)
    prefix_sum[0] = sgn(nums[0])
    occurrences[nums[0]] = [1]  # 存储位置索引（1-based）
    
    for i in range(1, len(nums)):
        prefix_sum[i] = prefix_sum[i-1]
        occ = occurrences.get(nums[i], [])
        if not occ:
            prefix_sum[i] += sgn(nums[i])
        occurrences[nums[i]] = occ + [i + 1]
    
    # 使用线段树优化查找
    seg = SegmentTree(prefix_sum)
    
    for i in range(len(nums)):
        # 查找从i开始的最长平衡子数组
        length = max(length, seg.find_last(i + length, 0) - i)
        
        # 更新occurrences
        next_pos = len(nums) + 1
        occurrences[nums[i]] = occurrences[nums[i]][1:]
        if occurrences[nums[i]]:
            next_pos = occurrences[nums[i]][0]
        
        # 区间更新：移除当前数字的影响
        seg.add(i + 1, next_pos - 1, -sgn(nums[i]))
    
    return length


def main():
    """测试函数"""
    nums = [2, 5, 4, 3]
    result = longest_balanced(nums)
    print(result)  # 预期输出：0？4？根据算法逻辑


if __name__ == "__main__":
    main()

C++完整代码如下：

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

class LazyTag {
public:
    int toAdd;

    LazyTag(int to_add = 0) : toAdd(to_add) {}

    LazyTag* add(LazyTag* other) {
        toAdd += other->toAdd;
        return this;
    }

    bool hasTag() const {
        return toAdd != 0;
    }

    void clear() {
        toAdd = 0;
    }
};

class SegmentTreeNode {
public:
    int minValue;
    int maxValue;
    LazyTag* lazyTag;

    SegmentTreeNode() : minValue(0), maxValue(0) {
        lazyTag = new LazyTag();
    }

    ~SegmentTreeNode() {
        delete lazyTag;
    }
};

class SegmentTree {
private:
    int n;
    vector<SegmentTreeNode*> tree;

    void applyTag(int i, LazyTag* tag) {
        tree[i]->minValue += tag->toAdd;
        tree[i]->maxValue += tag->toAdd;
        tree[i]->lazyTag->add(tag);
    }

    void pushdown(int i) {
        if (tree[i]->lazyTag->hasTag()) {
            LazyTag* tag = new LazyTag(tree[i]->lazyTag->toAdd);
            applyTag(i << 1, tag);
            applyTag((i << 1) | 1, tag);
            tree[i]->lazyTag->clear();
            delete tag;
        }
    }

    void pushup(int i) {
        tree[i]->minValue = min(tree[i << 1]->minValue, tree[(i << 1) | 1]->minValue);
        tree[i]->maxValue = max(tree[i << 1]->maxValue, tree[(i << 1) | 1]->maxValue);
    }

    void build(const vector<int>& data, int l, int r, int i) {
        if (l == r) {
            tree[i]->minValue = data[l - 1];
            tree[i]->maxValue = data[l - 1];
            return;
        }

        int mid = l + ((r - l) >> 1);
        build(data, l, mid, i << 1);
        build(data, mid + 1, r, (i << 1) | 1);
        pushup(i);
    }

    void update(int targetL, int targetR, LazyTag* tag, int l, int r, int i) {
        if (targetL <= l && r <= targetR) {
            applyTag(i, tag);
            return;
        }

        pushdown(i);
        int mid = l + ((r - l) >> 1);
        if (targetL <= mid) {
            update(targetL, targetR, tag, l, mid, i << 1);
        }
        if (targetR > mid) {
            update(targetL, targetR, tag, mid + 1, r, (i << 1) | 1);
        }
        pushup(i);
    }

    int find(int targetL, int targetR, int val, int l, int r, int i) {
        if (tree[i]->minValue > val || tree[i]->maxValue < val) {
            return -1;
        }

        if (l == r) {
            return l;
        }

        pushdown(i);
        int mid = l + ((r - l) >> 1);

        // 先查找右半部分
        if (targetR >= mid + 1) {
            int res = find(targetL, targetR, val, mid + 1, r, (i << 1) | 1);
            if (res != -1) {
                return res;
            }
        }

        // 再查找左半部分
        if (l <= targetR && mid >= targetL) {
            return find(targetL, targetR, val, l, mid, i << 1);
        }

        return -1;
    }

public:
    SegmentTree(const vector<int>& data) {
        n = data.size();
        tree.resize(n * 4 + 1);
        for (int i = 0; i <= n * 4; i++) {
            tree[i] = new SegmentTreeNode();
        }
        build(data, 1, n, 1);
    }

    ~SegmentTree() {
        for (auto node : tree) {
            delete node;
        }
    }

    void add(int l, int r, int val) {
        LazyTag* tag = new LazyTag(val);
        update(l, r, tag, 1, n, 1);
        delete tag;
    }

    int findLast(int start, int val) {
        if (start > n) {
            return -1;
        }
        return find(start, n, val, 1, n, 1);
    }
};

class Solution {
public:
    int longestBalanced(vector<int>& nums) {
        unordered_map<int, vector<int>> occurrences;

        auto sgn = [](int x) -> int {
            return (x % 2 == 0) ? 1 : -1;
        };

        int length = 0;
        int n = nums.size();
        vector<int> prefixSum(n);

        if (n == 0) return 0;

        prefixSum[0] = sgn(nums[0]);
        occurrences[nums[0]] = vector<int>{1};

        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1];
            auto& occ = occurrences[nums[i]];
            if (occ.empty()) {
                prefixSum[i] += sgn(nums[i]);
            }
            occ.push_back(i + 1);
        }

        SegmentTree seg(prefixSum);

        for (int i = 0; i < n; i++) {
            int found = seg.findLast(i + length, 0);
            if (found != -1) {
                length = max(length, found - i);
            }

            int nextPos = n + 1;
            auto& occ = occurrences[nums[i]];
            if (!occ.empty()) {
                occ.erase(occ.begin());
                if (!occ.empty()) {
                    nextPos = occ[0];
                }
            }

            seg.add(i + 1, nextPos - 1, -sgn(nums[i]));
        }

        return length;
    }
};

int main() {
    vector<int> nums = {2, 5, 4, 3};
    Solution solution;
    int result = solution.longestBalanced(nums);
    cout << result << endl;
    return 0;
}