问题背景

给你一个数组 $nums$ 和一个整数 $k$。你需要找到 $nums$ 的一个 子数组 ，满足子数组中所有元素按位或运算 $OR$ 的值与 $k$ 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 $nums[l..r]$ 满足 $|k-(nums[l]ORnums[l+1]...ORnums[r])|$ 最小。
请你返回 最小 的绝对差值。
子数组 是数组中连续的 非空 元素序列。

数据约束

• $1\le nums.length\le 10^5$
• $1\le nums[i]\le 10^9$
• $1\le k\le 10^9$

解题过程

这题是对数组元素进行某种操作后按照某种标准求子数组的模板题，这类问题的特点就是通常要求的操作没有逆运算，例如这里的或运算，它的逆运算是不容易实现的。
解决方案有两个，一是使用 LogTrick，找了一圈没找到出处在哪里，那还是贴一下 灵神题解。大体上思路是在嵌套循环的基础上，跳过明显不可能是结果的情形，有点像剪枝。在这题中，如果循环中遇到的新元素没能增加运算结果，那它也不可能在更大范围内产生不同的情形，可以跳出内层循环。
这种做法，可以将时间复杂度从 $O(N^2)$ 优化到 $O(NlogU)$，其中 $U$ 是数组中的最大值。

另一种思路当然是滑窗，需要解决元素排除出窗口这个操作的实现，实际上用到了类似栈的思想，数组 $nums[i]$ 记录的是 $nums[i]|nums[i-1]...|nums[0]$ 的结果。
多定义一个变量 $bottom$，避免不必要的数据更新操作。

具体实现

LogTrick

class Solution {public int minimumDifference(int[] nums, int k) {int res = Integer.MAX_VALUE;for(int i = 0; i < nums.length; i++) {int cur = nums[i];res = Math.min(res, Math.abs(cur - k));// 和暴力解的区别就在于多进行了一个判断，去掉了不必要的遍历for(int j = i - 1; j >= 0 && (nums[j] | cur) != nums[j]; j--) {nums[j] |= cur;res = Math.min(res, Math.abs(nums[j] - k));}}return res;}
}

滑动窗口

class Solution {public int minimumDifference(int[] nums, int k) {int res = Integer.MAX_VALUE;int bottom = 0;int rightOr = 0;for(int left = 0, right = 0; right < nums.length; right++) {// 元素从窗口右侧进入rightOr |= nums[right];while(left <= right && (nums[left] | rightOr) > k) {// 循环条件保证了 (nums[left++] | rightOr) 大于 k，相应地更新结果res = Math.min(res, (nums[left++] | rightOr) - k);// bottom 始终指向栈底，它在窗口之外表示 rightOr 的结果没有被 nums 数组记录if(bottom < left) {// 遍历并把结果更新到 nums 数组中for(int i = right - 1; i >= left; i--) {nums[i] |= nums[i + 1];}// 更新栈底指针bottom = right;// 重置右侧或运算结果rightOr = 0;}}// 内层循环结束，表示 left <= right 或 (nums[left] | rightOr) > k 条件被打破if(left <= right) {// 循环条件保证了 k 大于 (nums[left++] | rightOr)，在合法的情况下更新结果res = Math.min(res, k - (nums[left] | rightOr));}}return res;}
}