# 1521. 找到最接近目标值的函数值
### 题目地址（1521. 找到最接近目标值的函数值）
### 题目描述
```
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/)
我们也可以采用同样的思路进行枚举。
总的连续子数组按位与操作等于：以索引为 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 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1521.find-a-value-of-a-mysterious-function-closest-to-target.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.