leetcode forcebutton brushup 系列 - [按位或最接近 K 的位置查找子数组] - 答案

我的方法
方法有问题，这道题在力扣中属于难题，对我而言也不简单，我就是简单的先找到所有的子列表，再找到所有的or值，在进行绝对值的运算，这样子确实简单易懂，但是一旦nums足够大，我们的程序就会超出内存大小。
今天也是没有完成今天的题目，还是因为我太菜啦，想不到更牛的方法，所以今天还是分享一下官方大大的解题思路和方法吧。

class Solution(object):
    def minimumDifference(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # 获取数组中所有子数组的值
        subnums=[]
        result = []
        for i in range(len(nums)):
            for j in range(i,len(nums)):
                subnum = nums[i:j+1]
                subnums.append(subnum)
        # 算出每一个或运算的值
        for sublist in subnums:
            if len(sublist) == 1:
                result.append(sublist[0])
            else:
                or_result = sublist[0]
                for num in sublist[1:]:
                    or_result = or_result | num
                result.append(or_result)
        absnums = [abs(num - k) for num in result]
        return min(absnums)

注：我写的方法没啥用，并没有能通过测试

官方大大的方法
思路与算法
题目给定一个数组 nums 和一个整数 k。我们需要找到 nums 的一个非空子数组，要求其所有元素的或运算结果与 k 值尽可能接近。
根据或运算的性质，当我们固定子数组的右端点，不断地向左延伸左端点时，子数组或运算结果逐渐增加，并且结果种类数不超过 log(max(nums))+1 种。因为或运算结果每次增加对应于二进制表示中某些位上由 0 变为 1，因此增加的种类数受到数值范围的限制。

因此，我们从左到右遍历 nums，并在过程中记录每个二进制上的 1 出现的最晚的位置。这些位置用于我们在延伸左端点时，遍历所有种类的或运算结果。具体的，我们用 bits_max_pos[j] 来表示第 j 个二进制为 1 出现的最晚位置，在固定右端点后，将所有的二元组 (bits_max_pos[j],j) 从大到小排序，然后依次遍历这些二元组。遍历时将或运算结果与 2^j做或运算，得到新的结果，并计算其与 k 的差值。最终答案取所有差值的最小值。
需要注意的是，对于不同的 j，其 bits_max_pos[j] 可能相同，在计算区间或运算结果时需要将它们都考虑到，因此这里需要双指针去更新或运算结果。

代码

n = len(nums)
        bits_max_pos = [-1] * 31
        res = inf
        
        for i in range(n):
            for j in range(31):
                if nums[i] >> j & 1:
                    bits_max_pos[j] = i
            pos_to_bit = [(bits_max_pos[j], j) for j in range(31) if bits_max_pos[j] != -1]
            pos_to_bit.sort(reverse = True, key = lambda x: x[0])
            
            j, val = 0, 0
            while j < len(pos_to_bit):
                p = j
                while j < len(pos_to_bit) and pos_to_bit[j][0] == pos_to_bit[p][0]:
                    val |= 1 << pos_to_bit[j][1]
                    j += 1
                res = min(res, abs(val - k))
        
        return res