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

难度: Hard

Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。

请你返回 |func(arr, l, r) - target| 的最小值。

请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。

示例 1：

输入：arr = [9,12,3,7,15], target = 5
输出：2
解释：所有可能的 [l,r] 数对包括 [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]]， Winston 得到的相应结果为 [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0] 。最接近 5 的值是 7 和 3，所以最小差值为 2 。

示例 2：

输入：arr = [1000000,1000000,1000000], target = 1
输出：999999
解释：Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000 ，所以最小差值为 999999 。

示例 3：

输入：arr = [1,2,4,8,16], target = 0
输出：0

提示：

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
0 <= target <= 10^7

Submission

运行时间: 244 ms

内存: 29.8 MB

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        ands = set()
        prev = set()
        for x in arr:
            now = set()
            for y in prev:
                now.add(y & x)
            now.add(x)
            ands |= now
            prev = now
        return min(abs(x - target) for x in ands)

Explain

题解采用了动态规划的思想来解决问题。首先，初始化两个集合 `ands` 和 `prev`，其中 `ands` 用于存储所有可能的 `func(arr, l, r)` 的结果，`prev` 用于存储上一位置的所有可能的位与结果。遍历输入数组 `arr` 中的每个元素 `x`，对于每个元素，创建一个新集合 `now`。对于 `prev` 中的每个元素 `y`，将 `y & x` 的结果放入 `now` 集合中，同时将当前元素 `x` 也加入到 `now`。之后，将 `now` 中的所有元素加入到 `ands` 集合中。最后，遍历 `ands` 集合，找出与 `target` 的差的绝对值最小的结果。

时间复杂度: O(n * m)

空间复杂度: O(m)

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        ands = set()  # 存储所有可能的 func(arr, l, r) 结果
        prev = set()  # 存储上一位置的所有可能的位与结果
        for x in arr:  # 遍历数组中的每个元素
            now = set()  # 当前元素的所有可能的位与结果
            for y in prev:  # 遍历上一位置的位与结果
                now.add(y & x)  # 更新当前位与结果
            now.add(x)  # 将当前元素本身也加入
            ands |= now  # 更新所有可能的位与结果
            prev = now  # 将当前结果设为下一次的前一位置结果
        return min(abs(x - target) for x in ands)  # 返回最接近 target 的值的最小差值

Explore

在算法中使用集合（set）而不是列表（list）的主要原因是集合具有自动去重的特性。由于位与操作可能会产生重复的结果，如果使用列表存储，则可能会包含大量重复的结果，这会增加存储空间和处理时间。集合通过自动去重，可以有效减少存储需求和提高效率。此外，集合的查找、添加和删除操作通常是平均时间复杂度为O(1)，这对于此类问题来说更为高效。

在这个算法中，`prev` 集合的大小由位与操作的性质限制。由于位与操作的结果不能比操作数的位长更长，且随着位与操作的连续应用，结果中的1的数量通常会减少，这意味着可能的不同结果数量是有限的。例如，对于32位整数，最大的不同结果数量将受限于位模式的可能变化，这通常远小于32位所有可能的组合，从而形成一个实际上限。此上限与`arr`的值的范围和分布有关，但不直接依赖于`arr`的长度。

这一步骤通过系统地计算当前元素与前一个结果集合中元素的位与操作，确保了能够探索所有可能的位与结果。在每一轮循环中，新的元素`x`被与`prev`集合中的每个元素进行位与操作，这反映了加入新元素前的所有可能子数组的位与结果。通过将新元素单独加入结果集，同时保留了从当前元素开始的新子数组的可能性。这种组合确保了覆盖所有从任意位置开始到当前位置的子数组的位与结果。

虽然根据算法的设计，我们必须检查`ands`集合中的所有元素以找到最小的差值，但可以通过一些策略优化这一过程。例如，可以在计算过程中维护一个当前的最小差值和对应的元素值。在遍历`ands`集合时，如果发现当前元素与目标值`target`的差的绝对值大于已知的最小差值，可以跳过进一步的比较。此外，如果`ands`的大小可以预先限制或在运行时通过某些逻辑减少，也能进一步提高效率。但要注意的是，这些优化不能改变必须检查每个元素以保证找到最小差值的基本要求。