2588-统计美丽子数组数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

给你一个下标从 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 <= 105
  • 0 <= nums[i] <= 106

前置知识：前缀异或和

下文中 \oplus 表示异或运算

对于数组 nums，定义它的前缀异或和 s}[0]=0，s}[i+1] = \bigoplus\limits_{j=0}^{i}\textit{nums}[j]。

根据这个定义，有 s[i+1]=s[i]\oplus\textit{nums}[i]。

例如 nums}=[4,3,1,2,4]，对应的前缀异或和数组为 s=[0,4,7,6,4,0]。

通过前缀异或和，我们可以把子数组的异或和转换成两个前缀异或和的异或，即

\bigoplus_{j=\textit{left} }^{\textit{right} }\textit{nums}[j] = \bigoplus\limits_{j=0}^{\textit{right} }\textit{nums}[j] \oplus \bigoplus\limits_{j=0}^{\textit{left}-1}\textit{nums}[j] = \textit{s}[\textit{right}+1]\oplus \textit{s}[\textit{left}]

例如 nums 的子数组 [3,1,2] 的异或和就可以用 s[4]\oplus s[1]=4\oplus 4=0 算出来。

注：为方便计算，常用左闭右开区间 [\textit{left},\textit{right}) 来表示从 nums}[\textit{left}] 到 nums}[\textit{right}-1] 的子数组，此时子数组的异或和为 s}[\textit{right}] \oplus \textit{s}[\textit{left}]。

注 2：s[0]=0 表示一个空数组的异或和。为什么要额外定义它？想一想，如果要计算的子数组恰好是一个前缀（从 nums}[0] 开始），你要用 s[\textit{right}] 异或谁呢？通过定义 s[0]=0，任意子数组（包括前缀）都可以表示为两个前缀异或和的异或。

提示 1

由于每次操作的都是同一个比特位，可以把每一位单独看。

提示 2

每次都去掉两个 1，要是美丽子数组，需要子数组内这个比特位的 1 的个数是偶数。

提示 3

由于 1\oplus 1=0，把所有比特位合起来看，美丽子数组这等价于子数组的异或和等于 0。

提示 4

利用前缀异或和 s，问题相当于在求 s 中有多少对 s[\textit{left}] 和 s[\textit{right}] 满足 s[\textit{right}]\oplus s[\textit{left}] = 0，即 s[\textit{right}]= s[\textit{left}]，因为异或为 0 的两个数字必然相等。

也就是说，我们实际计算的是 s 中有多少对相同数字。

我们可以一边遍历 s，一边用一个哈希表 cnt 统计 s[i] 的出现次数，累加遍历中的 cnt}[s[i]]，即为答案。

附：视频讲解

[sol1-Python3]
1
2
3
4
5
6
7
8
9
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
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    long long beautifulSubarrays(vector<int> &nums) {
        long long ans = 0;
        int n = nums.size();
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i)
            s[i + 1] = s[i] ^ nums[i];
        unordered_map<int, int> cnt;
        for (int x : s)
            // 先计入答案再统计个数，如果反过来的话，就相当于把空子数组也计入答案了
            ans += cnt[x]++;
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
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
}

优化

也可以一边计算 s，一边统计答案。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
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
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    long long beautifulSubarrays(vector<int> &nums) {
        long long ans = 0;
        int s = 0;
        unordered_map<int, int> cnt{ {s, 1} }; // s[0]
        for (int x : nums) {
            s ^= x;
            ans += cnt[s]++;
        }
        return ans;
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
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
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 nums 的长度。
  • 空间复杂度：O(n)。

相似题目

推荐按顺序做。

 Comments
On this page
2588-统计美丽子数组数目
  1. 前置知识：前缀异或和
  2. 提示 1
  3. 提示 2
  4. 提示 3
  5. 提示 4
  6. 优化
  7. 复杂度分析
  8. 相似题目