[LeetCode] 2588. Count the Number of Beautiful Subarrays

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

统计美丽子数组数目。

给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：

• 选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
• 选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
• 将 nums[i] 和 nums[j] 都减去 2k 。

如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个 美丽 的子数组。

请你返回数组 nums 中 美丽子数组 的数目。

子数组是一个数组中一段连续 非空 的元素序列。

思路

思路是前缀和。注意题目要我们找的是子数组，子数组的特点是连续的。但是这种题一般不会允许你用O(n^2)的复杂度去解决，同时这道题还牵涉到如何把数字变成0，所以应该不是暴力解做。

我们可以把数字转换成二进制，看看是否能找到规律。比如对于数组[4,3,1,2,4]而言，他的二进制是

100
011
001
010
100

因为题目要求我们每次只能选择两个不同数字来把他们某一位上的 1 变成 0，那么我们可以看每一位上 1 的个数是否为偶数个。如果某一位上有奇数个 1 的话就不行，因为题目要求我们找的是连续的子数组。那么既然是找连续的子数组他们在某一位上 1 的个数为偶数个的话，我们就可以用前缀和的思路解决。如果某一些数字他们的前缀和为0的话，就说明他们的二进制表达在每一位上 1 的个数为偶数个。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public long beautifulSubarrays(int[] nums) {
        int n = nums.length;
        int[] presum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            presum[i + 1] = presum[i] ^ nums[i];
        }

        long count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n + 1; i++) {
            count += map.getOrDefault(presum[i], 0);
            map.put(presum[i], map.getOrDefault(presum[i], 0) + 1);
        }
        return count;
    }
}