位运算LogTrick

链接：https://leetcode.cn/problems/find-subarray-with-bitwise-or-closest-to-k/description/
困难：https://leetcode.cn/problems/smallest-subarrays-with-maximum-bitwise-or/description/?envType=daily-question&envId=2025-07-29

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

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

请你返回最小的绝对差值。

示例 1：输入：nums = [1,2,4,5], k = 3
输出：0

解释：子数组 nums[0..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。

示例 2：输入：nums = [1,3,1,3], k = 2
输出：1

解释：子数组 nums[1..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。

分析

我们首先想到的是暴力算法，外层循环，从 i=0 开始，从左到右遍历 nums。内层循环，从 j=i−1 开始，从右到左遍历 nums，更新 nums[j]=nums[j] ∣ nums[i]。

// 暴力算法，会超时
var minimumDifference = function(nums, k) {
    let ans = Infinity;
    for (let i = 0; i < nums.length; i++) { // 计算右端点为 i 的子数组的 OR
        const x = nums[i];
        ans = Math.min(ans, Math.abs(x - k)); // 单个元素也算子数组
        for (let j = i - 1; j >= 0; j--) {
            nums[j] |= x; // 现在 nums[j] = 原数组 nums[j] 到 nums[i] 的 OR
            ans = Math.min(ans, Math.abs(nums[j] - k));
        }
    }
    return ans;
};

这里做了很多无用功，把 nums[i] 对应的集合记作 Ai，如果 Ai是Aj的子集，那么内层循环还需要继续跑吗？不需要。如果 A i
已经是 Aj的子集，那么 Ai必然也是更左边的 A0,A1,A2,⋯,Aj−1的子集。既然 Ai都已经是这些集合的子集了，那么并入操作不会改变这些集合。

完全版

加一个条件即可，nums[j] | x !== nums[j]

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;
};

按位或最大的最小子数组长度

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个最小非空子数组，它的起始位置为 i （包含这个位置），同时有最大的按位或运算值。

换言之，令 Bij 表示子数组 nums[i…j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。
一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且最短子数组的长度。

思路

总体思路一致，外层由左到右进行遍历，内层从右往左进行遍历，注意Ai是Aj的子集的情况。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallestSubarrays = function(nums) {
    const n = nums.length;
    const ans = Array(n).fill(1);
    for(let i = 0;i < n;i++){
        let x = nums[i];
        for(let j = i - 1;j >= 0 && (nums[j] | x !== nums[j]);j--){
            nums[j] |= x;
            ans[j] = i - j + 1
        }
    }
    return ans;
};