【滑动窗口】个人练习-Leetcode-3171. Find Subarray With Bitwise OR Closest to K

题目链接：https://leetcode.cn/problems/find-subarray-with-bitwise-or-closest-to-k/description/

题目大意：给出一个数组nums[]和一个数k，找一个子列，使得这个子列区间内的元素的按位或操作后得到的数和k的差的绝对值最小。

思路：按位或只会把二进制上的0变为1，也就是只会增加，因此要固定区间的一个端点，像滑动窗口一样遍历做。但具体的实现方法其实没想到，题解也看得有点一知半解。

如果对nums[]从左往右遍历的话，相当于固定区间的右端点。先找出二进制的32个bit位里，在当前范围内，每个bit位最右的位置（在nums[]中）是哪里，记录在late[]中。

        for (int i = 0; i < n; i++) {
            int tmp = nums[i];
            int idx = 1;
            while (tmp) {
                if (tmp & 1) {
                    late[idx] = i;
                }
                tmp = tmp >> 1;
                idx++;
            }

随后对每一个（nums[]中位置，bit位）这样的pair进行排序，从大到小（这样排序的原因是：我们希望结果尽可能接近k，所以从【离右端点近(nums[]中位置大，靠右）】和【bit位高（数值大）】的先考虑）。

			posb.clear();
            for (int j = 31; j > 0; j--) {
                if (late[j] != -1)
                    posb.push_back(make_pair(late[j], j));
            }
            sort(posb.begin(), posb.end(), greater<pair<int, int>>());

最后一部分，计算当前最接近k的值。因为【不同的bit位所对应的nums[]中最右位置可能是相同的】，我们需要一个pre指针来记录上一个所考虑的最远位置。

			int j = 0, pre = 0;
            int val = 0;
            while (j < posb.size()) {
                while (j < posb.size() && posb[j].first == posb[pre].first) {
                    val |= 1 << (posb[j].second - 1);
                    j++;
                }
                res = min(res, abs(val - k));
                pre = j;
            }

完整代码

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> late(32, -1);
        vector<pair<int, int>> posb;

        int res = INT_MAX;
        for (int i = 0; i < n; i++) {
            int tmp = nums[i];
            int idx = 1;
            while (tmp) {
                if (tmp & 1) {
                    late[idx] = i;
                }
                tmp = tmp >> 1;
                idx++;
            }

            posb.clear();
            for (int j = 31; j > 0; j--) {
                if (late[j] != -1)
                    posb.push_back(make_pair(late[j], j));
            }
            sort(posb.begin(), posb.end(), greater<pair<int, int>>());
            int j = 0, pre = 0;
            int val = 0;
            while (j < posb.size()) {
                while (j < posb.size() && posb[j].first == posb[pre].first) {
                    val |= 1 << (posb[j].second - 1);
                    j++;
                }
                res = min(res, abs(val - k));
                pre = j;
            }
        }
        return res;
    }
};