日期: 2024 年 10 月 9 日

目标

给你一个数组 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 。

示例 3：

输入：nums = [1], k = 10
输出：9
解释：
只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9

思路

寻找子数组使子数组元素按位或运算的值 or 尽可能地接近 k，即求 |k - or| 的最小值。

暴力求解的基本逻辑是，外层枚举右端点，内层从后向前枚举左端点，使用 nums[j] 保存 子数组 [j, i] 的或值，通过判断 (nums[j] | right) != nums[j] 决定 right 是否对或值有贡献，如果没有贡献，那么可以不再继续向前枚举左端点，因为前面的或值已经累加了后面的值，如果对子数组 [j, i] 的或值没有贡献，那么对前面的 [j - 1, i] 包含了 [j, i] 的或值更没有贡献。

代码

/**
 * @date 2024-10-09 8:59
 */
public class MinimumDifference3171 {

    public int minimumDifference_v1(int[] nums, int k) {
        int n = nums.length;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int right = nums[i];
            for (int j = i - 1; j >= 0 && ((nums[j] | right) != nums[j]); j--) {
                nums[j] |= right;
                res = Math.min(res, Math.abs(nums[j] - k));
            }
            res = Math.min(res, Math.abs(right - k));
        }
        return res;
    }

}

性能