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

链接：3171.找到按位或最接近K的子数组
难度：Hard
标签：位运算、线段树、数组、二分查找
简介：返回 优质数对 的总数。

题解 1 - python

• 编辑时间：2024-10-10
• 执行用时：2499ms
• 内存消耗：30.93MB
• 编程语言：python
• 解法介绍：二进制存储，枚举右侧

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        bits = [0] * 32
        cur = l = 0
        n = len(nums)
        res = inf
        for r in range(n):
            for b in range(32):
                if nums[r] & (1 << b):
                    bits[b] += 1
                    if bits[b] == 1:
                        cur |= 1 << b
            res = min(res, abs(k - cur))
            while l < r and cur > k:
                for b in range(32):
                    if nums[l] & (1 << b):
                        bits[b] -= 1
                        if bits[b] == 0:
                            cur &= ~(1 << b)
                res = min(res, abs(k - cur))
                l += 1
        return res