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

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

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

题目描述

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 结尾的子数组个数，这无疑是完备的。

关于这点不熟悉的，也可以看下我的 【西法带你学算法】一次搞定前缀和

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

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

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

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

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

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

关键点

• 识别出函数 func 满足某种单调性

• 采用合适的枚举方法

代码

代码支持：Python3

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 啦。

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