代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
我们有一个非负整数数组 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题目求的是子数组按位或操作的结果的数量，如果我们枚举子数组的结束位置 $i$，那么以 $i-1$ 结尾的子数组按位或操作的结果的数量最多不超过 $32$ 个。这是因为，按位或是一个单调递增的操作。
因此，我们用一个哈希表 $ans$ 记录所有子数组按位或操作的结果，用一个哈希表 $s$ 记录以当前元素结尾的子数组按位或操作的结果，初始时 $s$ 只包含一个元素 $0$。
接下来，我们枚举子数组的结束位置 $i$，那么以 $i$ 结尾的子数组按位或操作的结果，是以 $i-1$ 结尾的子数组按位或操作的结果与 $a[i]$ 进行按位或操作的结果的集合，再加上 $a[i]$ 本身。我们用一个哈希表 $t$ 记录以 $i$ 结尾的子数组按位或操作的结果，然后我们更新 $s = t$，并将 $t$ 中的所有元素加入 $ans$。
最终，我们返回哈希表 $ans$ 中元素的数量即可。
时间复杂度 $O(n \times \log M)$，空间复杂度 $O(n \times \log M)$。其中 $n$ 和 $M$ 分别为数组长度和数组中元素的最大值。
class Solution:
def subarrayBitwiseORs(self, arr: List[int]) -> int:
s = {0}
ans = set()
for x in arr:
s = {x | y for y in s} | {x}
ans |= s
return len(ans)
class Solution {
public int subarrayBitwiseORs(int[] arr) {
Set<Integer> s = new HashSet<>();
s.add(0);
Set<Integer> ans = new HashSet<>();
for (int x : arr) {
Set<Integer> t = new HashSet<>();
for (int y : s) {
t.add(x | y);
}
t.add(x);
s = t;
ans.addAll(s);
}
return ans.size();
}
}
class Solution {
public:
int subarrayBitwiseORs(vector<int>& arr) {
unordered_set<int> s{{0}};
unordered_set<int> ans;
for (int& x : arr) {
unordered_set<int> t{{x}};
for (int y : s) {
t.insert(x | y);
}
s = move(t);
ans.insert(s.begin(), s.end());
}
return ans.size();
}
};
func subarrayBitwiseORs(arr []int) int {
ans := map[int]bool{}
s := map[int]bool{0: true}
for _, x := range arr {
t := map[int]bool{x: true}
for y := range s {
t[x|y] = true
}
s = t
for y := range s {
ans[y] = true
}
}
return len(ans)
}
function subarrayBitwiseORs(arr: number[]): number {
const s: Set<number> = new Set();
const ans: Set<number> = new Set();
for (const x of arr) {
const t: Set<number> = new Set();
for (const y of s) {
t.add(x | y);
}
t.add(x);
s.clear();
for (const y of t) {
s.add(y);
ans.add(y);
}
}
return ans.size;
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。