难度: Medium
我们有一个非负整数数组 arr 。
对于每个（连续的）子数组 sub = [arr[i], arr[i + 1], ..., arr[j]] （ i <= j），我们对 sub 中的每个元素进行按位或操作，获得结果 arr[i] | arr[i + 1] | ... | arr[j] 。
返回可能结果的数量。 多次出现的结果在最终答案中仅计算一次。
示例 1：
输入：arr = [0] 输出：1 解释： 只有一个可能的结果 0 。
示例 2：
输入：arr = [1,1,2] 输出：3 解释： 可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。 产生的结果为 1，1，2，1，3，3 。 有三个唯一值，所以答案是 3 。
示例 3：
输入：arr = [1,2,4] 输出：6 解释： 可能的结果是 1，2，3，4，6，以及 7 。
提示：
1 <= nums.length <= 5 * 1040 <= nums[i] <= 109运行时间: 398 ms
内存: 42.0 MB
class Solution:
def subarrayBitwiseORs(self, arr: List[int]) -> int:
ans = set()
s1 = set() # 记录以每个arr[i]结尾的子数组能获取到的所有按位或值
for x in arr:
s2 = {x}
for y in s1:
s2.add(y | x)
ans |= s2
s1 = s2
return len(ans)
这个题解采用了一个动态的方式来避免重复计算子数组按位或的结果。首先，使用一个集合ans来存储所有唯一的按位或结果。然后，对于每个元素x，用一个新集合s2来存储以x结尾的所有子数组的按位或结果。这里s2初始化包含元素x自身。对于上一步的结果集合s1，对其中每个元素y执行 y | x 操作，并将结果添加到s2中。这样可以确保考虑了所有以x结尾的子数组的按位或结果。最后，将s2中的所有结果合并到ans中，并更新s1为s2以供下一次循环使用。这个方法有效地利用了已有的按位或结果来生成新的结果，避免了冗余计算。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def subarrayBitwiseORs(self, arr: List[int]) -> int:
ans = set() # 用于存储所有唯一的按位或结果
s1 = set() # 存储以每个arr[i]结尾的子数组的所有按位或结果
for x in arr:
s2 = {x} # 初始化为只包含当前元素x的集合
for y in s1: # 遍历s1中的每个元素y
s2.add(y | x) # 将y和x的按位或结果添加到s2
ans |= s2 # 将s2的结果并入到ans中
s1 = s2 # 更新s1为当前的s2，为下一次迭代准备
return len(ans) # 返回ans中元素的数量，即不同的按位或结果的个数
在这个题解中，动态方式指的是使用集合来存储中间结果，并通过迭代的方式更新这些结果。具体来说，集合s1存储了到当前元素为止，所有以当前元素结尾的子数组的按位或结果。当处理新的元素x时，我们不需要重新计算从头开始的所有子数组，而是利用已经计算过的结果s1。新建一个集合s2，首先加入元素x，然后对于s1中的每个元素y，计算y|x并添加到s2中。这样，s2就包含了所有以新元素x结尾的子数组按位或结果，而无需重复计算之前元素的按位或结果。通过这种方式，算法避免了对已计算结果的重复计算，减少了计算量。
这么做的主要目的是保证s1总是包含以当前遍历到的元素x结尾的所有子数组的按位或结果。如果将s2的结果直接加入到s1中，s1就会包含不同元素结尾的子数组结果，这会导致在后续计算中产生重复和错误的结果。通过设置s1为s2，我们确保每次迭代都是基于最新的元素x，从而能正确生成所有以该元素结尾的子数组按位或结果。这样的处理保证了结果的正确性和算法的高效性。
按位或操作的特性是，一旦某个比特位在操作中变成了1，它在后续的按位或操作中将永远是1。这意味着随着操作的进行，生成的数字将趋向于稳定，即不会再有新的1比特位出现。因此，在处理较长的数组时，尽管子数组的数量是指数级增长的，但实际上由于按位或操作的这一性质，有效的不同结果的数量是有限的，通常远小于子数组的总数。这大大减少了需要处理的数据量，提高了算法的效率。