JZX轻语：简

LeetCode 893 - 子数组按位或操作

发表于2024年05月21日

#集合

对于这种子数组的特征问题，一般来说可以考虑前缀和思路。但由于or操作并不满足差分性质，所以需要使用一个集合ans来维护所有的非重复结果，以及一个数据结构last来存储以上一个元素结尾的所有子数组的按位或结果，然后再将last中所有的结果和当前的元素再异或一次，放进ans中，并更新last(还需要往后追加当前元素，作为长度为1的子数组)。一开始使用的是列表，但随着数组的变大，循环的量会逐渐变多，性能下滑严重；后面改为了set之后进行了去重。

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        unique = set()
        last = set()  # 上一个元素结尾的所有子数组的异或结果
        for num in arr:
            new = set()
            for i in last:
                new_or_res = i | num
                new.add(new_or_res)
                unique.add(new_or_res)
            
            # 自己本身也作为一个长度为1的子数组
            new.add(num)
            unique.add(num)
            last = new
        return len(unique)

超时的版本：

class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        unique = set()
        last = []
        for num in arr:
            for i in range(len(last)):
                last[i] |= num
                unique.add(last[i])
            last.append(num)
            unique.add(num)
        return len(unique)

闪念标签：LC

题目链接：https://leetcode.cn/problems/bitwise-ors-of-subarrays/