给你一个下标从 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 中没有任何美丽子数组。
方法一（超时）
class Solution {
public long beautifulSubarrays(int[] nums) {
//判断入参
int length = nums.length;
if (length == 0) return 0;
//题目解析：
//就是每次可以选择一个整数i，可以选择两个其他整数j,k将其减去2的i次方
//解题思路：
//通过观察和经验可知，该题目是对2的整数进行操作，则我们就可以认为该题目是要进行二进制操作
//将示例1和示例2转化为二进制，通过数学归纳法可以看出，满足条件的子数组其二进制每一位上1的个数相加都为整数
//解题的方法：动态规划，前缀和
long res = 0;
//获取nums中最大的数的二进制位数
Integer max = Arrays.stream(nums).boxed().max(Comparator.comparingInt(o -> o)).get();
int bitLength = Integer.toString(max, 2).length();
//创建dp数组
int[][] dp = new int[bitLength][length + 1];
//初始化数据
for (int i = 0;i < bitLength;i++){
for (int j = 1;j <= length;j++){
dp[i][j] = dp[i][j-1] + (nums[j-1] >> i & 1);
}
}
//外层循环
for (int i = 1;i <= length;i++){
//向前扫描
loop:for (int j = i - 1;j >= 0;j--){
//检查每一位上是否正确
for (int k = 0;k < bitLength;k++){
if (((dp[k][i] - dp[k][j]) & 1) == 1) continue loop;
}
res++;
}
}
return res;
}
}结果：
方法二（超时）
class Solution {
public long beautifulSubarrays(int[] nums) {
//判断入参
int length = nums.length;
if (length == 0) return 0;
//题目解析：
//就是每次可以选择一个整数i，可以选择两个其他整数j,k将其减去2的i次方
//解题思路：
//通过观察和经验可知，该题目是对2的整数进行操作，则我们就可以认为该题目是要进行二进制操作
//将示例1和示例2转化为二进制，通过数学归纳法可以看出，满足条件的子数组其二进制每一位上1的个数相加都为整数
//解题的方法：动态规划，前缀和
long res = 0;
int[] dp = new int[length+1];
//初始化
for (int i = 1;i <= length;i++){
dp[i] = dp[i-1] ^ nums[i-1];
}
//迭代进行检查
for (int i = 1;i <= length;i++){
for (int j = i - 1;j >= 0;j--){
if ((dp[i] ^ dp[j]) == 0) {
res++;
}
}
}
return res;
}
}结果：
方法三（通过）
class Solution {
public long beautifulSubarrays(int[] nums) {
//判断入参
int length = nums.length;
if (length == 0) return 0;
//题目解析：
//就是每次可以选择一个整数i，可以选择两个其他整数j,k将其减去2的i次方
//解题思路：
//通过观察和经验可知，该题目是对2的整数进行操作，则我们就可以认为该题目是要进行二进制操作
//将示例1和示例2转化为二进制，通过数学归纳法可以看出，满足条件的子数组其二进制每一位上1的个数相加都为整数
//解题的方法：动态规划，前缀和，哈希算法
long res = 0;
int[] dp = new int[length+1];
//初始化
for (int i = 1;i <= length;i++){
dp[i] = dp[i-1] ^ nums[i-1];
}
//用哈希进行记录（之前用^进行判断本质上也是在寻找相同的值）
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0;i <= length;i++){
map.merge(dp[i],1,(o,n)->o+1);
}
//进行计算
for (int i : map.values()){
//由数学归纳法可以发现，统计相同的值和最终结果的关系公式
//假设原数组为0，0，0，0，map中0:4
//最终结果为6,用双指针可知为3+2+1,等差数列求和公式即可解出
res += (long)(i-1) * i / 2;
}
return res;
}
}结果：
原题链接：