3171. 找到按位与最接近 K 的子数组

本文主要是介绍3171. 找到按位与最接近 K 的子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$找子数组，尽量以 i 为右端点找性质$
链接：Leetcode 400 周赛 D 题

位运算性质技巧

子数组的与值最多只有log(u)个，u=max_element(),
[l, r], [l+1,r], [l+2, r] …[r,r] 逻辑与值从右到左最多的变化就是
nums[r] -> nums[r]-一个二进制1， …所以最多log(nums[r])个不同的值
上面是以r1为右端点有log(nums[r1])个不同的值，那么复杂度就是nlog（max_element(nums)）。
code

class Solution {
public:int minimumDifference(vector<int>& nums, int k) {set<int> a;int n = nums.size(); int res = 1e9;for(int i = 0; i < n; i ++){res = min(res, abs(nums[i]-k));set<int> b;for(auto it : a){b.insert(it&nums[i]);res = min(res, abs((it&nums[i])-k));}a = b;a.insert(nums[i]);}return res;}
};

滑动窗口

因为要求子数组求与，所以数组长度越大值不增，长度越小值不减，所以具有单调性，我们可以用滑动窗口来写
code

const int N = 1e5 + 10;
int bits[N][32];
class Solution {
public:int minimumDifference(vector<int>& nums, int m) {int n = nums.size();memset(bits, 0, sizeof(bits));for(int i = 1; i <= n; i ++){for(int k = 0; k <= 30; k ++){if((nums[i-1] >> k) & 1){bits[i][k] ++;}}}// 滑动窗口，子数组单调性，越多越小 越小越大int l = 1, r = 1; int res = 1e9; int tem = 0;vector<int> a(33);for(; r <= n; r ++){int b = 0;for(int k = 0; k <= 30; k ++){if(bits[r][k]) a[k] ++;if(a[k] == (r-l+1)) b += (1 << k);}tem = b;res = min(res, abs(tem - m));while(l <= r && tem < m){for(int k = 0; k <= 30; k ++){if(bits[l][k]) a[k] --;}int b = 0;l ++;for(int k = 0; k <= 30; k ++){if(a[k] == r-l+1) b |= (1 << k);}tem = b;res = min(res, abs(tem - m));} }return res;}
};

扩展一下，这里是统计每个数字每位上1的个数，也可以用前缀和和st表来实现该部分功能，但写起来会更麻烦。

前缀和+二分

赛时想出来的思路，枚举子数组左端点两次二分找最接近k的值更新答案
code

const int N = 1e5 + 10;
int bits[N][32];
class Solution {
public:int minimumDifference(vector<int>& a, int k) {int n = a.size();for(int i = 1; i <= n; i ++){int j = i - 1;for(int k = 0; k <= 30; k ++){if((a[j] >> k) & 1) bits[i][k] = bits[i-1][k] + 1;else bits[i][k] = bits[i-1][k];   }}int res = 1e9;function<int(int, int)> fun = [&](int l, int r)->int{int y = 0;for(int i = 0; i <= 30; i ++){if((bits[r][i] - bits[l-1][i]) == (r-l+1)) y |= (1 << i);}return y;};function<bool(int, int, int)> check = [&](int l, int r, int fg) -> bool{if(fg == 1){if(fun(l, r) >= k) return true;//da yu x zui xiaoelse return false;}else{//xiao yu x zui daif(fun(l, r) <= k) return true;else return false;}};for(int i = 1; i <= n; i ++){int x = fun(i, i);if(x > k){int l = i, r = n;while(l < r){// 大于x的最小的int mid = (l+r+1) >> 1;if(check(i, mid, 1)){l = mid;}else{r = mid-1;}}res = min(res, abs(k - fun(i, l)));l = i, r = n;while(l < r)//小于x最大{int mid = (l + r) >> 1;if(check(i, mid, 2)){r = mid;}else{l = mid+1;}}res = min(res, abs(k - fun(i, l)));}else{res = min(res, k-x);}}return res;}
};