---

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

• 标签：位运算、线段树、数组、二分查找
• 难度：困难

题目链接

• 1521. 找到最接近目标值的函数值 - 力扣

题目大意

描述：定义函数 $func(arr, l, r) = arr[l] \& arr[l+1] \& \dots \& arr[r]$（按位与的结果）。给定数组 $arr$ 和目标值 $target$。

要求：返回 $|func(arr, l, r) - target|$ 的最小可能值。

说明：

• $1 \le arr.length \le 10^5$。
• $1 \le arr[i] \le 10^6$。
• $0 \le target \le 10^6$。

示例：

• 示例 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 。

解题思路

思路 1：位运算 + 集合去重

1. 核心思想

按位与运算的性质：随着参与与运算的元素增多，结果只会不变或变小（二进制位只能从 $1$ 变 $0$，不会从 $0$ 变 $1$）。

关键观察：

• 固定右端点 $r$，当左端点 $l$ 从 $r$ 向左移动时，$func(l, r)$ 的值是单调不增的（准确说是每个二进制位一旦变成 $0$ 就不会再变回 $1$）。
• 对于固定的 $r$，所有可能的 $func(l, r)$ 的值种数最多 $\log_2(\max(arr)) \le 20$ 种（因为每个位最多变化一次）。

利用这个性质，我们可以遍历右端点 $r$，同时维护一个集合 $cur$，表示以 $r$ 为右端点的所有可能与运算结果。

2. 具体步骤

第 1 步：初始化 $ans$ 为一个大数，$prev$ 为空集合。

第 2 步：遍历 $arr$ 中的每个元素 $x$：

• 创建新集合 $cur$，初始包含 $x$。
• 对于 $prev$ 中的每个值 $v$，计算 $v \& x$，加入 $cur$。
• 用 $cur$ 中的每个值更新 $ans = min(ans, |val - target|)$。
• $prev = cur$。

第 3 步：返回 $ans$。

3. 为什么集合大小不超过 20？

按位与运算每次只能将某些位从 $1$ 变为 $0$。一个数的二进制位最多 $\log_2(10^6) \approx 20$ 位。每次与运算只会让结果变小或不变。从 $arr[r]$ 开始向左扩展时，每个二进制位最多从 $1$ 变 $0$ 一次，因此不同的结果数不超过 $20$ 个。

4. 举例说明

以 $arr = [9, 12, 3, 7, 15], target = 14$ 为例：

• $r=0$，$x=9=1001_2$：$cur=\{9\}$，$|9-14|=5$。
• $r=1$，$x=12=1100_2$：$cur=\{12, 12\&9=8\}$，$|12-14|=2$，$|8-14|=6$。
• $r=2$，$x=3=0011_2$：$cur=\{3, 3\&12=0, 3\&8=0\}=\{3,0\}$，$|3-14|=11$，$|0-14|=14$。
• $r=3$，$x=7=0111_2$：$cur=\{7, 7\&3=3, 7\&0=0\}=\{7,3,0\}$，$|7-14|=7$。
• $r=4$，$x=15=1111_2$：$cur=\{15, 15\&7=7, 15\&3=3, 15\&0=0\}$，$|15-14|=1$。

最小值为 $1$。

5. 复杂度分析

• 每个元素最多产生 $20$ 个结果。
• 总时间 $O(n \times 20) = O(n)$。
• 空间 $O(20) = O(1)$。

思路 1：代码

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        ans = float('inf')
        prev = set()
        for x in arr:
            cur = {x}
            for v in prev:
                cur.add(v & x)
            for val in cur:
                ans = min(ans, abs(val - target))
            prev = cur
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \times \log(\max(arr))) \approx O(20n) = O(n)$。
• 空间复杂度：$O(\log(\max(arr))) = O(1)$。

---

思路 2：二分查找 + 线段树（理论可行，不推荐）

也可以用线段树维护区间与值，然后对每个左端点二分查找最接近 target 的右端点。但实现较复杂，且 $O(n \log n)$ 的效率不如集合去重法。