题目链接

英文链接：https://leetcode.com/problems/bitwise-ors-of-subarrays/

中文链接：https://leetcode-cn.com/problems/bitwise-ors-of-subarrays/

题目详述

我们有一个非负整数数组 A。

对于每个（连续的）子数组 B = [A[i], A[i+1], …, A[j]] （ i <= j），我们对 B 中的每个元素进行按位或操作，获得结果 A[i] | A[i+1] | … | A[j]。

返回可能结果的数量。（多次出现的结果在最终答案中仅计算一次。）

示例 1：

输入：[0]
输出：1
解释：
只有一个可能的结果 0 。

示例 2：

输入：[1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。

示例 3：

输入：[1,2,4]
输出：6
解释：
可能的结果是 1，2，3，4，6，以及 7 。

提示：

1 <= A.length <= 50000
0 <= A[i] <= 10^9

题目详解

运用 Set 来去重比较合适。
维护三个 Set，分别为 res, cur, next，分别代表结果集，当前循环的结果，下次循环的结果。
遍历数组，运用当前元素和 cur 生成 next，并把 next 加入到 res 中，更新 cur = next。
最终 res 中元素的数量就是结果。

public class LeetCode_00898 {

    public int subarrayBitwiseORs(int[] A) {
        Set<Integer> res = new HashSet<>();
        Set<Integer> cur = new HashSet<>();
        for (int a : A) {
            Set<Integer> next = new HashSet<>();
            for (Integer num : cur) {
                next.add(a | num);
            }
            next.add(a);
            res.addAll(next);
            cur = next;
        }
        return res.size();
    }
}

上面的那种方法在英文版 LeetCode 能通过，在中文版的 LeetCode 会超时，中文版的数据比较强。
事实上，由于每次进行的是 | 操作，经过运算，结果中二进制位 1 的数量不会减少，只可能维持不变或增加。当增加到最大值所占有的全部二进位全部为 1 时，再进行异或运算就不会产生新结果，可以直接停止。
可以首先找到数组最大值，再找到最大值所占的二进制位的掩码。
每当运用上一轮的结果生成这一轮的结果时，如果等于掩码，就不用继续下去了，因为之后的运算生成的结果都等于掩码，不会生成新的结果。

public class LeetCode_00898 {

    public int subarrayBitwiseORs(int[] A) {
        int maxVal = Arrays.stream(A).max().getAsInt();         // 得到最大值
        int mask = (Integer.highestOneBit(maxVal) << 1) - 1;    // 得到掩码
        Set<Integer> res = new HashSet<>();
        for (int i = 0; i < A.length; ++i) {
            int val = A[i];
            res.add(val);
            for (int j = i - 1; j >= 0 && val != mask; --j) {   // 等于掩码不用继续
                val |= A[j];
                res.add(val);
            }
        }
        return res.size();
    }
}