第 477 场周赛Q2——3755. 最大平衡异或子数组的长度

题目链接：3755. 最大平衡异或子数组的长度（中等）

算法原理：

👉对应力扣题解

解法：前缀状态匹配+哈希表

351ms击败13.05%

时间复杂度O(N)

①定义2个前缀状态变量：

前缀异或和tmp：数组开头到当前位置所有元素的异或结果

奇偶差diff：数组开头到当前位置的奇数个数-偶数个数，令遇奇数+1，遇偶数-1

②满足题意的条件推导

两位置间子数组的异或和为0：两个位置的tmp相等

两位置间子数组的奇偶数数量相等：两个位置的diff相等

③组合状态设计：

将(tmp,diff)作为前缀状态存进哈希表，并且把第一次出现的位置存进哈希表，因为题目要求返回的子数组长度最大，所以只需要存第一次出现的位置即可

④初始化：

哈希表预先存入状态(0,0)，对应前缀索引0，代表前0个元素的空数组，为首次状态匹配提供基准

Java代码：

class Solution { public int maxBalancedSubarray(int[] nums) { int tmp=0;//前缀异或和 int diff=0;//奇偶差 int ret=0; //哈希表存<”前缀异或，奇偶差“,首次出现的前缀索引> //当再次遇到相同的键时，说明tmp=0且奇偶数相同 Map<String,Integer> hash=new HashMap<>(); //记录初识状态 hash.put("0,0",0); for(int i=0;i<nums.length;i++){ //记录的是前k=i+1个元素的状态 int x=nums[i]; diff+=(x%2==1)?1:-1; tmp^=x; String s=tmp+","+diff; if(hash.containsKey(s)) ret=Math.max(ret,i+1-hash.get(s)); else //首次出现,直接扔进去 hash.put(s,i+1); } return ret; } }