今日学习记录
1. 3755. 最大平衡异或子数组的长度
关键词：前缀和 位运算
问题分析：
给出一个数组,找到这个数组中满足条件的最长连续子数组,要求子数组中的奇偶数相同,且子数组中元素按位异或为 0
核心思路:
对于奇偶数相同,当遇到奇数时加一,偶数时减一,找到最长的相同前缀值
子数组中的所有元素异或和为 0,则s[l]=s[r]就代表从 l 到 r 中间按位异或为 0
实现细节
我们看来要捆绑两个信息,奇偶数和目前的元素按位异或值 我们可以使用 pair 来存储,但是要使用 map 我们可以使用位运算技巧用 long long 存储两个信息,前 int 存 cnt,后 int 存 sum,可以使用 unordered_map 进行存储,速度更快
**最终代码：
int maxBalancedSubarray(vector<int>& nums) {
unordered_map<long long,int> mp;
mp[0] = 0;
int ans = 0;
long long sum = 0;
long long cnt = 0;
for(int i = 0;i<nums.size();i++){
sum ^= nums[i];
cnt += (nums[i]&1?1:-1);
long long key = 1LL*cnt<<32|sum;
if(mp.count(key)) ans = max(ans,i-mp[key]+1);
else mp[key] = i+1;
}
return ans;
}学到的点：
- 无谋