题目描述

现在有一个非负整数数组A，对于A的每个连续子数组B = [A[i], A[i+1], …, A[j]] (i <= j)，我们对B中所有元素进行或运算，得到结果 A[i] | A[i+1] | … | A[j].
计算可能的结果的个数（重复出现的结果只计算一次）

注意：
1 <= A.length <= 50000
0 <= A[i] <= $10^9$

样例

输入: [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，一共6个不同的结果所以返回6.

算法1

(动归) $O(32N)$

用动归数组dp[i][j]记录从i到j的子数组的数字进行或操作的结果，那么dp[i][j+1]=dp[i][j]|A[j]，但是由于$O(n^2)$复杂度过高会超时，因此我们需要进行优化。

假设我们已经得到了列表B[j]=[dp[0][j],dp[1][j],…,dp[j][j]]，那么只需要将列表中每个元素与A[j+1]进行或，则得到了B[j+1]=[dp[0][j+1],dp[1][j+1],…,dp[j][j+1],A[j+1]]，由于我们只考虑不同的结果的个数，那么我们来看B[j]会有多少个不同的元素。从位操作角度来考虑，由于或操作只会增加位中1的个数，例如c=a|b，那么c的二进制位的1的个数不会小于a的二进制位的1的个数。由于元素不大于$10^9$，在int型范围内，所以B[j]中的每个元素的二进制位的1的个数不会超过32个，因此B[j]包含的不同的元素个数不会多于32个。因此，这样做实际上复杂度为$O(32N)$。

时间复杂度分析：$O(32N)$

C++ 代码

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& A) {
        if(A.empty())
            return 0;
        unordered_set<int>ans,B1,B2;
        for(int i = 0;i<A.size();i++){//在第i轮循环 B1=[dp[0][i-1],dp[1][i-1],...,dp[i-1][i-1]]
            for(int num:B1)           //B2=[dp[0][i],dp[1][i],...,dp[i][i]]
                B2.insert(num|A[i]);
            B2.insert(A[i]);
            B1=B2;
            for(int num:B2)
                ans.insert(num);
            B2.clear();  
        }
        return ans.size();
    }
};