以下是 LeetCode 3721. 最长平衡子数组 II 的 C 实现。---核心思路问题转化子数组中不同偶数个数 不同奇数个数 ⇔ 把每个不同的奇数记为 1每个不同的偶数记为 -1则子数组平衡 ⇔ 前缀和之差为 0。关键难点同一个数字重复出现时它只贡献一次去重但位置变了。需要用线段树维护动态变化的前缀和数组支持1. 区间加撤销旧贡献 添加新贡献2. 线段树上二分找最左等于目标值的位置算法流程- 枚举右端点 i1-indexed- 若 nums[i] 之前出现过撤销其在旧位置的贡献- 在当前位置 i 添加贡献- 用线段树查询最早出现相同前缀和的位置 pos- 更新答案 ans max(ans, i - pos)---C 代码cpp#include bits/stdc.husing namespace std;/*** LeetCode 3721. 最长平衡子数组 II** 核心思路线段树 前缀和 哈希表** 关键转化* - 每个不同的奇数贡献 1每个不同的偶数贡献 -1* - 维护前缀和 now 不同奇数个数 - 不同偶数个数* - 子数组 [l, r] 平衡 等价于 prefix[r] - prefix[l-1] 0* - 即 prefix[r] prefix[l-1]** 难点处理数字重复出现时需要撤销之前位置的贡献* - 用线段树维护前缀和数组支持区间加* - 用线段树上二分找最左等于目标值的位置*/// 线段树节点// 维护区间 [l, r] 的最小值 mn、最大值 mx 和懒标记 lazystruct Node {int l, r; // 区间范围int mn, mx; // 区间最小值 / 最大值前缀和int lazy; // 懒标记区间加Node() : l(0), r(0), mn(0), mx(0), lazy(0) {}};// 线段树// 支持// 1. 区间加// 2. 线段树上二分找最小索引使得前缀和等于 targetclass SegmentTree {private:vectorNode tr; // 线段树数组4倍空间// 对节点 u 应用区间加 vvoid apply(int u, int v) {tr[u].mn v;tr[u].mx v;tr[u].lazy v;}// 从子节点更新父节点void pushup(int u) {tr[u].mn min(tr[u 1].mn, tr[u 1 | 1].mn);tr[u].mx max(tr[u 1].mx, tr[u 1 | 1].mx);}// 下传懒标记void pushdown(int u) {if (tr[u].lazy ! 0) {apply(u 1, tr[u].lazy);apply(u 1 | 1, tr[u].lazy);tr[u].lazy 0;}}// 建树初始所有前缀和为 0void build(int u, int l, int r) {tr[u].l l;tr[u].r r;tr[u].mn tr[u].mx tr[u].lazy 0;if (l r) return;int mid (l r) 1;build(u 1, l, mid);build(u 1 | 1, mid 1, r);}public:// 创建线段树区间为 [0, n]SegmentTree(int n) {tr.resize((n 1) 2);build(1, 0, n);}// 区间 [l, r] 全部加 vvoid modify(int u, int l, int r, int v) {if (tr[u].l l tr[u].r r) {apply(u, v);return;}pushdown(u);int mid (tr[u].l tr[u].r) 1;if (l mid) modify(u 1, l, r, v);if (r mid) modify(u 1 | 1, l, r, v);pushup(u);}// 线段树上二分// 找最小索引 pos 使得前缀和 target// 关键观察如果 target 在 [mn, mx] 范围内则该区间内一定存在这样的位置int query(int u, int target) {if (tr[u].l tr[u].r) {return tr[u].l;}pushdown(u);int left u 1;int right u 1 | 1;if (tr[left].mn target target tr[left].mx) {return query(left, target);}return query(right, target);}};class Solution {public:int longestBalanced(vectorint nums) {int n nums.size();SegmentTree st(n);// last[x] 数值 x 上次出现的位置unordered_mapint, int last;int now 0; // 当前前缀和int ans 0; // 答案// 枚举子数组右端点1-indexedfor (int i 1; i n; i) {int x nums[i - 1];// x 的贡献奇数 1偶数 -1int det (x 1) ? 1 : -1;// 如果 x 之前出现过撤销其之前的贡献auto it last.find(x);if (it ! last.end()) {st.modify(1, it-second, n, -det);now - det;}// 添加当前 x 的贡献last[x] i;st.modify(1, i, n, det);now det;// 找最早出现相同前缀和的位置int pos st.query(1, now);ans max(ans, i - pos);}return ans;}};---复杂度分析项目 复杂度每次 modify O(\log n)每次 query O(\log n)总时间 O(n \log n)空间 O(n)线段树 4n 节点 哈希表---示例验证示例 1nums [2,5,4,3]i x det 操作 now pos ans1 2 -1 modify[1,4]-1 -1 1 02 5 1 modify[2,4]1 0 0 23 4 -1 modify[3,4]-1 -1 1 24 3 1 modify[4,4]1 0 0 4最长平衡子数组 [2,5,4,3]长度 4 ✓示例 2nums [3,2,2,5,4]- i3 时 x2 重复出现撤销 i2 的贡献在 i3 重新添加- 最终 ans 5子数组 [3,2,2,5,4] ✓示例 3nums [1,2,3,2]- i4 时 x2 重复出现撤销 i2 的贡献在 i4 重新添加- 最终 ans 3子数组 [2,3,2] ✓---下载完整 C 文件[solution_3721.cpp](sandbox:///mnt/agents/output/solution_3721.cpp)