2018-09-23 19:05:20

问题描述：

问题求解：

显然的是暴力的遍历所有的区间是不可取的，因为这样的时间复杂度为n^2级别的，对于规模在50000左右的输入会TLE。

然而，最后的解答也可以看作是一个暴力求解，也就是用Set来保存以当前数为结尾的左右可能解，在下一轮中遍历上一轮的所有解并进行或操作。

这里有个难以一下想到的地方就是，乍一看，这个时间复杂度依然是平方级别的，但是实际上，这里的时间复杂度是n级别的，因为Set中后一个数中的1完全覆盖前一个数，因此，最多只有不超过30个数在Set中，因此整个时间复杂度依然是线性的时间复杂度。

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