1521. 找到最接近目标值的函数值
题目地址（1521. 找到最接近目标值的函数值）
题目描述
1
Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。
2
3
请你返回 |func(arr, l, r) - target| 的最小值。
4
5
请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。
6
7
8
9
示例 1：
10
11
输入：arr = [9,12,3,7,15], target = 5
12
输出：2
13
解释：所有可能的 [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 。
14
示例 2：
15
16
输入：arr = [1000000,1000000,1000000], target = 1
17
输出：999999
18
解释：Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000 ，所以最小差值为 999999 。
19
示例 3：
20
21
输入：arr = [1,2,4,8,16], target = 0
22
输出：0
23
24
25
提示：
26
27
1 <= arr.length <= 10^5
28
1 <= arr[i] <= 10^6
29
0 <= target <= 10^7
Copied!
前置知识
- 位运算
- 动态规划
公司
- 暂无
思路
首先我们要知道一个前提，那就是对于一个数组 arr，对 arr 的子数组 arr[l:r] 进行与操作满足单调性，也就是说 arr[l:r] >= arr[l+1:r] >= arr[l+2:r] ... 。其中的依据是一个数异或另外一个数的结果一定不会比这两个数大。
为了更好的理解本题。我们可以从一个简单的例子入手。
题目描述：
1
如果让你求一个数组的连续子数组总个数，你会如何求？其中连续指的是数组的索引连续。 比如 [1,3,4]，其连续子数组有：[1], [3], [4], [1,3], [3,4] , [1,3,4]，你需要返回 6。
Copied!
一种思路是总的连续子数组个数等于：以索引为 0 结尾的子数组个数 + 以索引为 1 结尾的子数组个数 + … + 以索引为 n - 1 结尾的子数组个数，这无疑是完备的。
我们也可以采用同样的思路进行枚举。
总的连续子数组按位与操作等于：以索引为 0 结尾的子数组按位与操作的结果, 以索引为 1 结尾的子数组按位与操作的结果 + … + 以索引为 n - 1 结尾的子数组按位与操作的结果，这无疑是完备的。
而题目我求的不是总和，而是与 target 最接近的，不过这不难，使用一个全局变量记录即可。
以索引为 i 结尾的子数组按位与操作的结果 sub[i] 其实就等于
sub[i-1] & A[i]。这提示我们使用滚动数组来完成。而由于重复数字是没有意义的，因此可使用 hashset 来优化，而不是普通的数组，这样可以同时降低时间和空间复杂度。关于滚动数组可以参考我之前写的动态规划章节
这种解法其实就是暴力求解，和动态规划没有啥区别。
关键点
- 识别出函数 func 满足某种单调性
- 采用合适的枚举方法
代码
代码支持：Python3
1
class Solution:
2
def closestToTarget(self, A: List[int], target: int) -> int:
3
seen = set()
4
ans = float('inf')
5
for a in A:
6
seen.add(a)
7
t = set()
8
# 类似滚动数组 此时的 seen 相当于 sub[i-1]
9
for b in seen:
10
yu = a & b
11
ans = min(ans, abs(yu - target))
12
t.add(yu)
13
# 此时的 t 就是 sub[i]，我们需要更新回 seen
14
seen = t
15
return ans
Copied!
复杂度分析 令 N 为数组长度, C 为 seen 的大小。C 的大小和数据范围有关，在这里 C 不会超过 32。
- 时间复杂度：$O(N*C)$
- 空间复杂度：$O(C)$
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago