2026-04-09: 最大平衡异或子数组的长度。用go语言, 给定一个整数
发布日期：2026-04-29 18:52 点击次数：73
2026-04-09：最大平衡异或子数组的长度。用go语言，给定一个整数数组 nums，需要找出满足两项要求的最长连续子数组，并返回它的长度：
1.这个子数组内部所有元素做按位异或（XOR）运算的结果为 0。
2.这个子数组中，偶数的个数与奇数的个数必须相同（两者数量一致）。
如果整个数组中不存在同时满足以上条件的子数组，则返回 0。
1
0
输入： nums = [3,1,3,2,0]。
输出： 4。
解释：
子数组 [1, 3, 2, 0] 的按位异或为 1 XOR 3 XOR 2 XOR 0 = 0，且包含 2 个偶数和 2 个奇数。
题目来自力扣3755。
一、先明确两个核心条件的转化（解题关键）
题目要求子数组同时满足：
1. 异或和为 0
2. 偶数个数 = 奇数个数
我们把这两个条件转化为前缀特征，用两个核心指标记录：
1. 前缀异或值：从数组开头到当前位置，所有元素的异或累计结果（用于判断异或和为0）。
2. 奇偶差值：定义规则 → 遇到奇数加1，遇到偶数减1（最终差值为0，说明奇偶数量相等）。
只有两个前缀的「前缀异或值」完全相同 + 「奇偶差值」完全相同，这两个前缀之间的子数组，就同时满足题目两个条件。
二、初始化准备
1. 我们用一个哈希表存储「前缀异或值+奇偶差值」组合第一次出现的位置，方便后续快速查找。
2. 初始状态：数组还没遍历任何元素（空前缀），前缀异或值=0，奇偶差值=0，这个组合的位置记为 -1（这是算法的基准起点）。
3. 初始化当前前缀异或值、当前奇偶差值都为0，最终答案长度初始为0。
三、逐元素遍历数组，分步执行过程
数组元素依次是：索引0(3)、索引1(1)、索引2(3)、索引3(2)、索引4(0)
第一步：遍历索引0，元素=3
1. 3是奇数：更新当前前缀异或值（0 ^ 3 = 3），更新当前奇偶差值（0 + 1 = 1）。
2. 组合：(异或=3，差值=1)，哈希表中没有这个组合。
3. 把这个组合和当前索引0存入哈希表。
4. 无匹配，答案长度保持0。
第二步：遍历索引1，元素=1
1. 1是奇数：更新当前前缀异或值（3 ^ 1 = 2），更新当前奇偶差值（1 + 1 = 2）。
2. 组合：(异或=2，差值=2)，哈希表中没有这个组合。
3. 把这个组合和当前索引1存入哈希表。
4. 无匹配，答案长度保持0。
第三步：遍历索引2，元素=3
1. 3是奇数：更新当前前缀异或值（2 ^ 3 = 1），更新当前奇偶差值（2 + 1 = 3）。
2. 组合：(异或=1，差值=3)，哈希表中没有这个组合。
3. 把这个组合和当前索引2存入哈希表。
4. 无匹配，答案长度保持0。
第四步：遍历索引3，元素=2
1. 2是偶数：更新当前前缀异或值（1 ^ 2 = 3），更新当前奇偶差值（3 - 1 = 2）。
2. 组合：(异或=3，差值=2)，哈希表中没有这个组合。
3. 把这个组合和当前索引3存入哈希表。
4. 无匹配，答案长度保持0。
第五步：遍历索引4，元素=0
1. 0是偶数：更新当前前缀异或值（3 ^ 0 = 3），更新当前奇偶差值（2 - 1 = 1）。
2. 组合：(异或=3，差值=1) → 这个组合在哈希表中存在！第一次出现在索引0。
3. 计算子数组长度：当前索引4 - 第一次出现的索引0 = 4。
4. 答案长度更新为4。
四、最终结果
遍历结束，最长满足条件的子数组长度为4，对应子数组[1,3,2,0]（索引1到索引4）。
复杂度分析
1. 时间复杂度
整个算法只需要遍历数组一次，哈希表的插入、查找操作都是 O(1) 级别。
总时间复杂度：O(n)
• n 是数组的长度，无论数组多大，执行时间和数组长度成正比。
2. 额外空间复杂度
额外空间仅用于存储哈希表，哈希表最多存储n个不同的组合（极端情况所有前缀组合都不重复）。
总额外空间复杂度：O(n)
• 不包含输入数组本身，仅算法运行时需要的临时存储空间。
总结
1. 核心逻辑：用前缀异或+奇偶差值的组合，快速定位同时满足两个条件的子数组；
2. 执行过程：一次遍历+哈希表查找，无重复计算；
3. 效率：时间O(n)、空间O(n)，完美适配题目10万长度的数组要求。
Go完整代码如下：
package main
import (
"fmt"
)
func maxBalancedSubarray(nums []int) (ans int) {
type pair struct{ xor, diff int }
pos := map[pair]int{{}: -1} // 空前缀的位置视作 -1
p := pair{}
for i, x := range nums {
p.xor ^= x
p.diff += x%2*2 - 1
if j, ok := pos[p]; ok {
ans = max(ans, i-j)
} else {
pos[p] = i
}
}
return
}
func main {
nums := []int{3, 1, 3, 2, 0}
result := maxBalancedSubarray(nums)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def maxBalancedSubarray(nums):
ans = 0
# Use a dictionary to store the first occurrence of each (xor, diff) pair
pos = {(0, 0): -1} # Empty prefix position is -1
xor = 0
diff = 0
for i, x in enumerate(nums):
xor ^= x
diff += (x % 2) * 2 - 1 # Convert even/odd to -1/1
key = (xor, diff)
if key in pos:
ans = max(ans, i - pos[key])
else:
pos[key] = i
return ans
def main:
nums = [3, 1, 3, 2, 0]
result = maxBalancedSubarray(nums)
print(result)
if __name__ == "__main__":
main
C++完整代码如下：
#include
#include
#include
#include
using namespace std;
struct Pair {
int xor_val;
int diff;
bool operator
if (xor_val != other.xor_val) return xor_val
return diff
}
};
int maxBalancedSubarray(vector& nums) {
int ans = 0;
map
// Empty prefix position is -1
pos[{0, 0}] = -1;
Pair p = {0, 0};
for (int i = 0; i
int x = nums[i];
p.xor_val ^= x;
p.diff += (x % 2) * 2 - 1;
if (pos.find(p) != pos.end) {
ans = max(ans, i - pos[p]);
} else {
pos[p] = i;
}
}
return ans;
}
int main {
vector nums = {3, 1, 3, 2, 0};
int result = maxBalancedSubarray(nums);
cout
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
上一篇：日媒: 中国车企销量首次登顶, 将终结日系车多年“销冠”地位
下一篇：没有了