统计美丽子数组数目

You are given a 0-indexed integer array nums. In one operation, you can:

• Choose two different indices i and j such that 0 <= i, j < nums.length.
• Choose a non-negative integer k such that the kth bit (0-indexed) in the binary representation of nums[i] and nums[j] is 1.
• Subtract 2k from nums[i] and nums[j].

A subarray is beautiful if it is possible to make all of its elements equal to 0 after applying the above operation any number of times.

Return the number of beautiful subarrays in the array nums.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [4,3,1,2,4]
Output: 2
Explanation: There are 2 beautiful subarrays in nums: [4,3,1,2,4] and [4,3,1,2,4].
- We can make all elements in the subarray [3,1,2] equal to 0 in the following way:
  - Choose [3, 1, 2] and k = 1. Subtract 21 from both numbers. The subarray becomes [1, 1, 0].
  - Choose [1, 1, 0] and k = 0. Subtract 20 from both numbers. The subarray becomes [0, 0, 0].
- We can make all elements in the subarray [4,3,1,2,4] equal to 0 in the following way:
  - Choose [4, 3, 1, 2, 4] and k = 2. Subtract 22 from both numbers. The subarray becomes [0, 3, 1, 2, 0].
  - Choose [0, 3, 1, 2, 0] and k = 0. Subtract 20 from both numbers. The subarray becomes [0, 2, 0, 2, 0].
  - Choose [0, 2, 0, 2, 0] and k = 1. Subtract 21 from both numbers. The subarray becomes [0, 0, 0, 0, 0].

Example 2:

Input: nums = [1,10,4]
Output: 0
Explanation: There are no beautiful subarrays in nums.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 106

/*
 * 思路：
 * 1. 使用流式操作来简化代码，按与运算来实现。
 * 2. 通过二进制按位运算可以发现，如果子数组内所有元素的按位与运算结果为0，则该子数组可以通过若干次操作变为全0数组。
 * 3. 使用前缀和数组来记录每个位置的按位与运算结果，
 *    如果在两个位置之间的按位与结果为0，则这部分子数组是美丽的。
 */
import java.util.stream.*;
import java.util.*;

public class Solution {
    public int beautifulSubarrays(int[] nums) {
        int[] prefixXor = IntStream.rangeClosed(0, nums.length)
                                    .map(i -> IntStream.range(0, i).reduce(0, (a, b) -> a ^ nums[b]))
                                    .toArray();
        Map<Integer, Integer> countMap = new HashMap<>();
        return IntStream.of(prefixXor)
                        .map(xor -> countMap.merge(xor, 1, Integer::sum) - 1)
                        .sum();
    }
}

本题解采用了异或和哈希表的方法来检测美丽子数组。核心思想是使用异或运算的性质：任何数与自身异或的结果为0，以及异或运算的可交换性。遍历数组，计算从第一个元素到当前元素的异或累积结果 num。如果在某个位置的异或累积结果 num 已经出现在哈希表 Map 中，说明从前一个相同异或结果的位置到当前位置的子数组异或结果为0，即这个子数组可以通过上述操作全部变为0，因此是一个美丽子数组。Map 中存储的是每个异或结果出现的次数，这样可以在找到重复的异或结果时，直接通过 Map[num] 获取到当前异或结果之前出现的次数，这些都是以当前位置结尾的美丽子数组的起始位置的候选。初始时，Map 中加入 {0:1} 来表示一个虚拟的前缀，以支持从数组开始到当前位置的异或结果就是0的情况。

O(n)

O(n)