发表于 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 题目链接