1521. 找到最接近目标值的函数值

https://leetcode-cn.com/problems/find-a-value-of-a-mysterious-function-closest-to-target/

这题有点类似"使用双指针寻找子数组之和等于某个值"的问题

这个问题我们只需要记录 arr[l..r] 上所有的bits数值就可以还原

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:

        n = len(arr)

        def getBits(x):
            bits = [0] * 32
            for i in range(32):
                if (x >> i) & 0x1:
                    bits[i] += 1
            return bits

        def addBits(x, y):
            for i in range(32):
                x[i] += y[i]

        def subBits(x, y):
            for i in range(32):
                x[i] -= y[i]

        def cons(bits, size):
            t = 0
            for i in range(32):
                if bits[i] == size:
                    t |= (1 << i)
            return t

        BITS = [0] * 32
        t = arr[0]
        j = 0
        ans = 1 << 30
        for i in range(n):
            x = arr[i]

            t = t & x
            bits = getBits(x)
            addBits(BITS, bits)

            # print(t)
            ans = min(ans, abs(t - target))

            if t < target:
                while j < i and t < target:
                    y = arr[j]
                    bits = getBits(y)
                    subBits(BITS, bits)
                    t = cons(BITS, i - j)
                    # print(t)
                    ans = min(ans, abs(t - target))
                    j += 1

        return ans