Links

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 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。