[leetcode] 2588. 统计美丽子数组数目

题目描述

leetcode.cn/problems/…/description

数据范围

• $1 \leq nums.length \leq 10^5$

• $0 \leq nums[i] \leq 10^6$

思路

很经典的一道题, 之前在cf上写过原题(cf指codeforces).

首先, 题目要求选择任意两个数, 减去他们在二进制下的第k位是$1$的值, 写成式子的话大概长这样, $(1\underbrace{00...00}_{k})_{b}$. 右下角的$b$表示这个是二进制下的数, 很明显减去的这个数就是$2^k$.

如果数只有两位的话要让这样的两个数变成$0$, 很简单, 只要两个数相等就行了.

但是如果不只两位呢, 对于$[1,2,3]$这样的一个数组, 应该可以直接看出来, 这个数组是"美丽数组", 选择$1$和$3$, 一起减去$2^0$,原数组变成$[0,2,2]$. 再选择两个$2$, 一起减去$2^1$, 最后都变成$0$.

但是, 使用一个一个去减的方法是不可能实现的, 因为数据范围太大了, $10^5$级的数据需要的时间复杂度不能超过$O(nlog_n)$, 需要一个其他的方法.

因为需要减去的是在二进制下的第k位, 换个理解方式, 把上面的例子写成二进制的形式重复一边操作.

不知道你看出来规律没有, 每次的操作都是取两个数, 在对应的位置上减去$1$.

这样看可能不太明显, 把三个数相加, 不考虑进位, 得到的值是$22$. 就像上面说的那样, 每次操作在一个位置上减去$2$, $22$正好在两次的操作之后可以被全部归零...

有了上面的结论之后这道题就变得非常简单了, 分别枚举一个起点和一个终点, 举例出所有的方案, 然后看每个方案相加是否每一位上都是偶数就好了.

but...还是上面的问题, 就算使用前缀和优化之后, 枚举区间的这一步的复杂度还是$O(n^2)$级的, 会$TLE$(运行超时), 还需要进一步优化.

是否有一种方法不需要枚举区间呢...欸, 还真有, 记得上面说的前缀和吗, 使用前缀和的方法将每一位分别相加, 看这个位置上是不是偶数就可以知道这个位置上有没有被归零了.

说起计算偶数, 还记得那几个位运算吗, 可以使用异或, 如果两个都是$1$, 异或在一起就变成$0$了, 如果其中一个是$1$那么得到的还是$1$. 那么直接看最后的数是不是全是$0$就可以判断是不是美丽数组了.

但是, 就算是前缀和还是逃不过计算区间的梦魇, 有没有方法可以省去这步呢, 如果能知道要怎样可以让当前这个数变成零的话就很方便了.

那么是不是可以记录下当前位置的前缀异或和呢, 如果后面有数异或这个位置上的前缀异或和的得到的结果是$0$的话, 那么也可以说明单前位置到后面那个数也是一个美丽子数组.

到这里思路已经很明确了, 直接开一个哈希表记录每个位置上的前缀异或和, 如果在后面的计算中得到了一样的异或值, 就可以表明这是一个美丽子数组, 加入答案中.

代码

rust:

impl Solution {
    pub fn beautiful_subarrays(nums: Vec<i32>) -> i64 {
        let mut mp: std::collections::HashMap<i32, i32> = std::collections::HashMap::new();
        let mut ans: i64 = 0;
        let mut xor_sum: i32 = 0; // 前缀异或和

        // 初始化
        mp.insert(0, 1);

        for &num in &nums {
            xor_sum ^= num;

            // 如果出现相同的前缀异或和
            // 好抽象的语法...
            // 因为 mp.get() 返回的是 Option<&i32> 类型
            // 可能有值, 也可能没有, 需要用 let Some(&count) 来接收
            // if let Some(&count) = ... 是 rust 的模式匹配语法
            // &count 将引用解构为具体的值
            // if 只在返回 Some 里的值的时候执行里面的语句
            if let Some(&count) = mp.get(&xor_sum) {
                ans += count as i64;
            }

            // 更新出现次数
            // mp.entry(xor_sum) 访问具体的条目, 返回一个 Entry 对象
            // or_insert(0) 如果值存在, 返回可变引用
            // 如果不存在就插入一个值0, 再返回一个可变引用
            // mp前的 * 表示解引用, 配合后面的 += 1更改这个值
            *mp.entry(xor_sum).or_insert(0) += 1;
        }
        ans
    }
}

py:

class Solution:
    def beautifulSubarrays(self, nums: List[int]) -> int:
        mp = {}
        ans = 0
        xor_sum = 0

        # 初始化
        mp[0] = 1

        for i in range(len(nums)):
            xor_sum ^= nums[i]
            ans += mp.get(xor_sum, 0)
            mp[xor_sum] = mp.get(xor_sum, 0) + 1
        return ans

碎碎念:

最近写rust写的有点爆炸, 明明在py里随便就能写完的, 在rust里总是要写很长一大串, 然后还有一些奇奇怪怪的语法, 乍一看还以为是来搞笑的...(没错, 说的就是上面那个在if语句里赋值的操作).

而且还有很多异常处理和类型转换相关的操作, 写的头大.(可怜我那本就仅存不多的头发了)

感觉就是很不适合用来写题目, 写题最强的应该还是c艹, STL简直无敌, 而且运行速度也快.