[3171] 找到按位或最接近 K 的子数组

暴力解法

超时

details

var minimumDifference = function (nums, k) {
    let size = nums.length;
    let minDiff = Infinity;

    for (let i = 0; i < size; i++) {
        let acc = 0;
        for (let j = i; j < size; j++) {
            acc |= nums[j];
            let diff = Math.abs(acc - k);
            if (diff < minDiff) {
                minDiff = diff;
            }
            if (acc !== nums[j] || diff >= k) break;
        }
    }
    return minDiff;
};

滑动窗口

details

var minimumDifference = function (nums, k) {
    let ans = Infinity;
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        ans = Math.min(ans, Math.abs(x - k));
        // 如果 x 是 nums[j] 的子集，就退出循环
        for (let j = i - 1; j >= 0 && (nums[j] | x) !== nums[j]; j--) {
            nums[j] |= x;
            ans = Math.min(ans, Math.abs(nums[j] - k));
        }
    }
};
return ans;