Leetcode3171. 找到按位与最接近 K 的子数组

Every day a Leetcode

解法1：位运算

在这里插入图片描述

优化：

在这里插入图片描述

代码：

/*
 * @lc app=leetcode.cn id=3171 lang=cpp
 *
 * [3171] 找到按位与最接近 K 的子数组
 */

// @lc code=start
class Solution
{
public:
    int minimumDifference(vector<int> &nums, int k)
    {
        int n = nums.size();
        int ans = INT_MAX;
        for (int i = 0; i < n; i++)
        {
            int x = nums[i];
            ans = min(ans, abs(x - k));
            for (int j = i - 1; j >= 0; j--)
            {
                if ((nums[j] & x) == nums[j])
                    break;
                nums[j] &= x;
                ans = min(ans, abs(nums[j] - k));
            }
        }
        return ans;
    }
};
// @lc code=end

结果：

在这里插入图片描述

复杂度分析：

时间复杂度：O(nlogU)，其中 n 是数组 nums 的长度，U=max⁡(nums)。

空间复杂度：O(1)。