微帮推广平台有哪些_日本门户网站_百度指数分析工具_2021最近最火的关键词

• 分析问题

• 题意： 找出所有 所有元素异或和为0 的子数组。（子数组是在原数组中连续的子序列）
• 每次操作都是选取元素的同一位不为0的二进制位异或为0，所以，能够多次操作后变为全0的数组的 所有元素异或和一定为0。

• 方案一

复杂度：$O(n^2)$
实现方法：创建一个异或和数组，用这个数组计算 美丽子数组

class Solution {
public:long long beautifulSubarrays(vector<int>& nums) {long long ans = 0;vector<int> v;v.push_back(0);v.push_back(nums[0]);for (int i = 1; i < nums.size(); i++) {v.push_back(v[i] ^ nums[i]);}for (int i = 0; i < v.size(); i++) {for (int j = i + 1; j < v.size(); j++) {if (!(v[i] ^ v[j])) {ans++;}}}return ans;}
};

• 方案二

方案一 复杂度太高了，优化方法：从左往右遍历前缀和数组，用一个hash表维护前缀和数组中的值，累加与当前下标元素值相同的元素数量。

class Solution {
public:long long beautifulSubarrays(vector<int>& nums) {long long ans = 0;vector<int> v;v.push_back(nums[0]);map<int, long long> mp;for (int i = 1; i < nums.size(); i++) {v.push_back(v[i-1] ^ nums[i]);cout << v[i] << " ";}for (int i = 0; i < v.size(); i++) {long long t = mp[v[i]];ans += t;if (mp[v[i]]) mp[v[i]]++;else mp[v[i]] = 1;if (!v[i]) ans++;}return ans;}
};