题目描述

func(arr, l, r) {
    if (r < l) {
        return -1000000000;
    }
    ans = arr[l]
    for (i = l + 1; i < r; i++) {
        ans = ans & arr[i]
    }
    return ans
}

Winston 构造了一个如上所示的函数 func。他有一个整数数组 arr 和一个整数 target，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r。

请你返回 |func(arr, l, r) - target| 的最小值。

请注意，func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length。

样例

输入：arr = [9,12,3,7,15], target = 5
输出：2
解释：所有可能的 [l,r] 数对包括

[[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],
 [2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]]，

Winston 得到的相应结果为 [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]。
最接近 5 的值是 7 和 3，所以最小差值为 2。

输入：arr = [1000000,1000000,1000000], target = 1
输出：999999
解释：Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000，所以最小差值为 999999。

输入：arr = [1,2,4,8,16], target = 0
输出：0

限制

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^6
• 0 <= target <= 10^7

算法

(双指针) $O(n \log S)$

1. 我们发现，区间长度越大，按位与得到的结果就越小。
2. 对于每个区间右端点 r，我们找到尽可能小的 l，满足区间按位与大于等于 target。
3. 我们发现，随着 r 向右移动，l 是单调不减的，所以我们可以采用双指针。
4. 这里和一般的双指针不一样的是，按位与没有逆操作，即我们在向后移动 l 的过程中，需要将最左侧的数字剔除掉，但这一步操作没有常数时间的做法。这里我们用一个位数组 cnt，来记录每一位上 0 的个数，这样就可以求出新的区间按位与了。

时间复杂度

• 每个位置仅遍历两次，每次移动 l 或者 r 所需要的时间复杂度是 $O(\log S)$，这里的 $S$ 是最大的数字。
• 故总时间复杂度位 $O(n \log S)$

空间复杂度

• 需要 $O(\log S)$ 的额外空间存储每一位上 0 的个数。

C++ 代码

class Solution {
private:
    const static int m = 24;

    void add(vector<int> &cnt, int x, int &sum) {
        for (int i = 0; i < m; i++)
            if (!((x >> i) & 1)) {
                cnt[i]++;
                if (cnt[i] == 1)
                    sum ^= 1 << i;
            }
    }

    void remove(vector<int> &cnt, int x, int &sum) {
        for (int i = 0; i < m; i++)
            if (!((x >> i) & 1)) {
                cnt[i]--;
                if (cnt[i] == 0)
                    sum |= 1 << i;
            }
    }

public:
    int closestToTarget(vector<int>& arr, int target) {
        int n = arr.size();
        vector<int> cnt(m, 0);

        int ans = INT_MAX, sum = (1 << m) - 1;
        for (int l = 0, r = 0; r < n; r++) {
            add(cnt, arr[r], sum);
            ans = min(ans, abs(sum - target));

            while (sum < target) {
                remove(cnt, arr[l++], sum);
                ans = min(ans, abs(sum - target));
            }
        }

        return ans;
    }
};