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

### 题目地址（1521. 找到最接近目标值的函数值）

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

### 题目描述

![](https://p.ipic.vip/1mscqi.jpg)

```
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


```

### 前置知识

* 位运算
* 动态规划

### 公司

* 暂无

### 思路

首先我们要知道一个前提，那就是对于一个数组 arr，对 arr 的子数组 arr\[l:r] 进行与操作满足单调性，也就是说 arr\[l:r] >= arr\[l+1:r] >= arr\[l+2:r] ... 。其中的依据是**一个数异或另外一个数的结果一定不会比这两个数大**。

为了更好的理解本题。我们可以从一个简单的例子入手。

题目描述：

```
如果让你求一个数组的连续子数组总个数，你会如何求？其中连续指的是数组的索引连续。 比如 [1,3,4]，其连续子数组有：[1], [3], [4], [1,3], [3,4] , [1,3,4]，你需要返回 6。
```

一种思路是总的连续子数组个数等于：以索引为 0 结尾的子数组个数 + 以索引为 1 结尾的子数组个数 + … + 以索引为 n - 1 结尾的子数组个数，这无疑是完备的。

> 关于这点不熟悉的，也可以看下我的 [【西法带你学算法】一次搞定前缀和](https://lucifer.ren/blog/2020/09/27/atMostK/)

![](https://p.ipic.vip/1sv0hv.jpg)

我们也可以采用同样的思路进行枚举。

总的连续子数组按位与操作等于：以索引为 0 结尾的子数组按位与操作的结果, 以索引为 1 结尾的子数组按位与操作的结果 + … + 以索引为 n - 1 结尾的子数组按位与操作的结果，这无疑是完备的。

而题目我求的不是总和，而是与 target 最接近的，不过这不难，使用一个全局变量记录即可。

以索引为 i 结尾的子数组按位与操作的结果 sub\[i] 其实就等于 `sub[i-1] & A[i]`。这提示我们使用滚动数组来完成。而由于重复数字是没有意义的，因此可使用 hashset 来优化，而不是普通的数组，这样可以同时降低时间和空间复杂度。

> 关于滚动数组可以参考我之前写的动态规划章节

这种解法其实就是暴力求解，和动态规划没有啥区别。

### 关键点

* 识别出函数 func 满足某种单调性
* 采用合适的枚举方法

### 代码

代码支持：Python3

```python
class Solution:
    def closestToTarget(self, A: List[int], target: int) -> int:
        seen = set()
        ans = float('inf')
        for a in A:
            seen.add(a)
            t = set()
            # 类似滚动数组 此时的 seen 相当于 sub[i-1]
            for b in seen:
                yu = a & b
                ans = min(ans, abs(yu - target))
                t.add(yu)
            # 此时的 t 就是 sub[i]，我们需要更新回 seen
            seen = t
        return ans
```

**复杂度分析** 令 N 为数组长度, C 为 seen 的大小。C 的大小和数据范围有关，在这里 C 不会超过 32。

* 时间复杂度：$O(N\*C)$
* 空间复杂度：$O(C)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/jqnd01.jpg)
