C++ 子数组位运算结果 题型
或运算
898. 子数组按位或操作 - 力扣（LeetCode）
我们直接看题，意思很明显，就是找出所有子数组，然后将子数组各个数相或得到的结果有多少个不同。
这里我们首先想到的就是直接把所有子数组求出来在或起来，但显然有很多的重复计算。我们在算[1,2] 和[1,2,3]时，完全可以直接用[1,2]的结果继续算。因此有了优化思路。这里我直接告诉优化的思路参考了LogTrick 入门教程 - 知乎。
可以将子数组分成以i下标开始的子数组。例如在数组[4,3,2,1,0]中，我们可以将结果分成以4,3,2,1,0下标为开始的子数组。
那么我们如何完整求出所有以i下标开始的子数组呢？那也很好求了，我们只要让以i开始的后面数挨个或在i下标的数组上，每次计算后就统计，这样就能将所有情况统计到了。
这里我们直接给代码，方便大家理解我说的逻辑：
int subarrayBitwiseORs(vector<int>& arr) { unordered_set<int>st;//去重 int len=arr.size(); for(int l = 0; l < len ; ++l){ st.insert(arr[l]);//只有一个数也要统计 for(int r = l-1;r>=0; --r){ arr[r] = arr[r]|arr[l];//看不懂的可以看下面的注释 st.insert(arr[r]); } } return st.size(); } // 3 2 1 0 // 3 //下标在0 // 3|2 2 //下标在1 // 3|2|1 2|1 1 //2 // 3|2|1|0 2|1|0 1|0 0 //3这样就能统计全部的结果了。但是也有问题，时间复杂度是O(n²)
我们再看题目要求，它要统计的是所有不同的数。我们看注释表。
例如看2|1，2|1 == 2意思就是这次的1不起作用，那么我们对前面的3|2|1是否起作用呢？答案是也不起作用，另前面的式子等于 n|2|1 因为2|1=2不起作用，所以根本不影响n。因此我们可以提前结束
int subarrayBitwiseORs(vector<int>& arr) { unordered_set<int>st; int len=arr.size(); for(int l = 0; l < len ; ++l){ st.insert(arr[l]); for(int r = l-1;r>=0 && (arr[r]|arr[l])!=arr[r]; --r){ arr[r] = arr[r]|arr[l]; st.insert(arr[r]); } } return st.size(); }那么时间复杂度是多少呢，如果每次arr[r] | arr[l]都能不等于arr[l]，那么说明至少产生了一个新的位置1，如果每次都是至少置1，而int的位数去除符合位，最多只有31次。因此可以说明是常数级别，粗糙的看成O(n)。
那么这个方式可以用到相同情况的题目上：
2411. 按位或最大的最小子数组长度 - 力扣（LeetCode）
这里大家可以先自己做一下，因为思路差不多就不多赘述。
class Solution { public: vector<int> smallestSubarrays(vector<int>& nums) { int num=0,len = nums.size(); vector<pair<int,int>>ret(len); for(int i=0;i<len;++i){ ret[i]={nums[i],1}; for(int j = i-1;j>=0&&((nums[j]|nums[i])!=nums[j]);--j){ nums[j]|=nums[i]; if(nums[j]>ret[j].first)ret[j]={nums[j],i-j+1}; } } vector<int>ans; for(auto[_,k]:ret)ans.emplace_back(k); return ans; } };3171. 找到按位或最接近 K 的子数组 - 力扣（LeetCode）
class Solution { public: int minimumDifference(vector<int>& nums, int k) { int ret = 0x3f3f3f3f,len=nums.size(); for(int i=0;i<len;++i){ ret= min(abs(k-nums[i]),ret); for(int j=i-1;j>=0&&((nums[j]|nums[i])!=nums[j]);--j){ nums[j]|=nums[i]; ret= min(abs(k-nums[j]),ret); } } return ret; } };与运算
那么我们能否推而广之用到与运算的这种求子数组运算值的呢？可以的！
int AND(vector<int>& arr) { int len=arr.size(); for(int l = 0; l < len ; ++l){ for(int r = l-1;r>=0&&(arr[r]&arr[l])!=arr[r]; --r){ arr[r] = arr[r]&arr[l]; st.insert(arr[r]); } } return ...; } // 0 1 2 // 0 // 0&1 1 // 0&1&2 1&2 2如果出现arr[l]&arr[r] ==arr[r] 说明arr[l]集合更大，且r左边的集合会更小，完全用不到arr[l]。因此可以提前退出。
时间复杂度依旧最坏情况O(n)*31，粗糙来看就是O(n)。