Leetcode 2588. Count the Number of Beautiful Subarrays

[Woodyiiiiiii]

推理一步步来，首先关键是所谓的“operation”，显然不可能找到每个数值对相同的二进制1然后相减，所以一定要将这个条件简化一下。

那么基本上是位运算了，既然是同位的1，一开始我想的是&与。但细细转换下思维，两个数会消除同位1，这不就是^异或吗。所以这个难点就可以转换成求所有连续子数组使得他们的异或结果为0。

这种连续子数组模型的解法，排除了滑动窗口后，就想到用前缀和Map。这种类似的题目还有：

• 560. Subarray Sum Equals K
• 1590. Make Sum Divisible by P
• ...

class Solution {
    public long beautifulSubarrays(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int tmp = 0;
        long ans = 0;
        for (int num : nums) {
            tmp ^= num;
            if (map.containsKey(tmp)) {
                ans += map.get(tmp);
            }
            map.put(tmp, map.getOrDefault(tmp, 0) + 1);
        }
        return ans;
    }
}

---

• 2588. Count the Number of Beautiful Subarrays