[数据结构与算法]LeetCode 898. 子数组按位或操作 - set

898. 子数组按位或操作
     我们有一个非负整数数组 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 * 104
0 <= nums[i] <= 109???????

题解

不断用set去重，一开始先写了个暴力版的，想着可能会超时，没想到过了，瑟瑟发抖。

AC代码

class Solution {
public:
    set<int>q,q2,q3;
    int subarrayBitwiseORs(vector<int>& arr) 
    {
        q.insert(arr[0]);
        q3.insert(arr[0]);
        for(int i=1;i<arr.size();i++)
        {
            q2 = q3;
            q3.clear();
            set<int>::iterator it = q2.begin();
            while(it!=q2.end())
            {
                q3.insert(*it|arr[i]);
                q.insert(*it|arr[i]);
                it++;
            }
            q3.insert(arr[i]);
            //储存自己本身
            q.insert(arr[i]);
        }
        int ans = 0;
        set<int>::iterator it = q.begin();
        while(it!=q.end())
        {
            ans ++;
            it++;
        }
        return ans;
    }
};