class Solution {
public:
long long beautifulSubarrays(vector<int>& nums) {
}
};
6317. 统计美丽子数组数目
给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：
0 <= i, j < nums.length 的不同下标 i 和 j 。k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。nums[i] 和 nums[j] 都减去 2k 。如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。
请你返回数组 nums 中 美丽子数组 的数目。
子数组是一个数组中一段连续 非空 的元素序列。
示例 1：
输入：nums = [4,3,1,2,4] 输出：2 解释：nums 中有 2 个美丽子数组：[4,3,1,2,4] 和 [4,3,1,2,4] 。 - 按照下述步骤，我们可以将子数组 [3,1,2] 中所有元素变成 0 ： - 选择 [3, 1, 2] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [1, 1, 0] 。 - 选择 [1, 1, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 0, 0] 。 - 按照下述步骤，我们可以将子数组 [4,3,1,2,4] 中所有元素变成 0 ： - 选择 [4, 3, 1, 2, 4] 和 k = 2 。将 2 个数字都减去 22 ，子数组变成 [0, 3, 1, 2, 0] 。 - 选择 [0, 3, 1, 2, 0] 和 k = 0 。将 2 个数字都减去 20 ，子数组变成 [0, 2, 0, 2, 0] 。 - 选择 [0, 2, 0, 2, 0] 和 k = 1 。将 2 个数字都减去 21 ，子数组变成 [0, 0, 0, 0, 0] 。
示例 2：
输入：nums = [1,10,4] 输出：0 解释：nums 中没有任何美丽子数组。
提示：
1 <= nums.length <= 1050 <= nums[i] <= 106原站题解
python3 解法, 执行用时: 264 ms, 内存消耗: 36 MB, 提交时间: 2023-03-13 09:29:06
class Solution:
def beautifulSubarrays(self, nums: List[int]) -> int:
ans = s = 0
cnt = Counter({s: 1}) # s[0]
for x in nums:
s ^= x
ans += cnt[s]
cnt[s] += 1
return ans
java 解法, 执行用时: 60 ms, 内存消耗: 53.7 MB, 提交时间: 2023-03-13 09:28:48
class Solution {
public long beautifulSubarrays(int[] nums) {
long ans = 0;
int s = 0;
var cnt = new HashMap<Integer, Integer>();
cnt.put(s, 1); // s[0]
for (int x : nums) {
s ^= x;
ans += cnt.getOrDefault(s, 0);
cnt.merge(s, 1, Integer::sum);
}
return ans;
}
}
golang 解法, 执行用时: 204 ms, 内存消耗: 12.4 MB, 提交时间: 2023-03-13 09:28:35
func beautifulSubarrays(nums []int) (ans int64) {
s := 0
cnt := map[int]int{s: 1} // s[0]
for _, x := range nums {
s ^= x
ans += int64(cnt[s])
cnt[s]++
}
return
}
golang 解法, 执行用时: 176 ms, 内存消耗: 12.4 MB, 提交时间: 2023-03-13 09:28:27
func beautifulSubarrays(nums []int) (ans int64) {
s := make([]int, len(nums)+1)
for i, x := range nums {
s[i+1] = s[i] ^ x
}
cnt := map[int]int{}
for _, x := range s {
// 先计入答案再统计个数，如果反过来的话，就相当于把空子数组也计入答案了
ans += int64(cnt[x])
cnt[x]++
}
return
}
java 解法, 执行用时: 47 ms, 内存消耗: 51.3 MB, 提交时间: 2023-03-13 09:28:09
class Solution {
public long beautifulSubarrays(int[] nums) {
long ans = 0;
int n = nums.length;
var s = new int[n + 1];
for (int i = 0; i < n; ++i)
s[i + 1] = s[i] ^ nums[i];
var cnt = new HashMap<Integer, Integer>();
for (int x : s) {
// 先计入答案再统计个数，如果反过来的话，就相当于把空子数组也计入答案了
ans += cnt.getOrDefault(x, 0);
cnt.merge(x, 1, Integer::sum);
}
return ans;
}
}
python3 解法, 执行用时: 332 ms, 内存消耗: 37 MB, 提交时间: 2023-03-13 09:27:54
'''
前缀异或和
'''
class Solution:
def beautifulSubarrays(self, nums: List[int]) -> int:
s = list(accumulate(nums, xor, initial=0))
ans, cnt = 0, Counter()
for x in s:
# 先计入答案再统计个数，如果反过来的话，就相当于把空子数组也计入答案了
ans += cnt[x]
cnt[x] += 1
return ans