How does binary search apply to this problem?

Binary search is used to efficiently explore the valid space of potential solutions for the indices `l` and `r`. By narrowing down the search space, we can find the closest possible function result to the target value.

What role does the mysterious function `func` play?

The function `func(arr, l, r)` calculates a value based on the subarray `arr[l...r]`, and the goal is to minimize the difference between this result and the given target.

Why is array manipulation important in this problem?

Array manipulation helps optimize the process of evaluating `func(arr, l, r)` by exploiting properties such as cumulative values or patterns that can be reused, reducing unnecessary recalculations.

What are the common mistakes when solving this problem?

Misunderstanding how binary search fits into the problem's structure or not optimizing the function calculations can lead to inefficient solutions that fail to handle larger inputs effectively.

What is the best approach for solving this problem efficiently?

The best approach combines binary search over the valid answer space with efficient manipulation of subarrays and function optimizations, ensuring the solution works within the given constraints.

#1521

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

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

Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。请你返回 |func(arr, l, r) - target| 的最小值。请注意， func 的输入…

数组二分查找位运算线段树

题目描述

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

lightbulb

解题思路

方法一：哈希表 + 枚举

根据题目描述，我们知道，函数 $func(arr, l, r)$ 实际上就是数组 $arr$ 下标 $l$ 到 $r$ 的元素的按位与运算的结果，即 $arr[l] \& arr[l + 1] \& \cdots \& arr[r]$ 。

如果我们每次固定右端点 $r$ ，那么左端点 $l$ 的范围是 $[0, r]$ 。由于按位与之和随着 $l$ 的减小而单调递减，并且 $arr[i]$ 的值不超过 $10^6$ ，因此区间 $[0, r]$ 最多只有 $20$ 种不同的值。因此，我们可以用一个集合来维护所有的 $arr[l] \& arr[l + 1] \& \cdots \& arr[r]$ 的值。当我们从 $r$ 遍历到 $r+1$ 时，以 $r+1$ 为右端点的值，就是集合中每个值与 $arr[r + 1]$ 进行按位与运算得到的值，再加上 $arr[r + 1]$ 本身。因此，我们只需要枚举集合中的每个值，与 $arr[r]$ 进行按位与运算，就可以得到以 $r$ 为右端点的所有值，将每个值与 $target$ 相减后取绝对值，就可以得到以 $r$ 为右端点的所有值与 $target$ 的差的绝对值，其中的最小值就是答案。

时间复杂度 $O(n \times \log M)$ ，空间复杂度 $O(\log M)$ 。其中 $n$ 和 $M$ 分别是数组 $arr$ 的长度和数组 $arr$ 中的最大值。

相似题目：

3171. 找到按位与最接近 K 的子数组

1

2

3

4

5

6

7

8

9

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        ans = abs(arr[0] - target)
        s = {arr[0]}
        for x in arr:
            s = {x & y for y in s} | {x}
            ans = min(ans, min(abs(y - target) for y in s))
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding of binary search and how to adapt it to a range of answers is crucial.
question_mark
The ability to optimize through recognizing patterns in array manipulation.
question_mark
Efficiently managing the evaluation of subarrays and ensuring that the approach scales well with larger inputs.

warning

常见陷阱

外企场景

error
Misunderstanding the binary search pattern for this problem could lead to inefficient solutions.
error
Failing to optimize the calculation of `func(arr, l, r)` could result in excessive computation time.
error
Not taking full advantage of array properties like the 'and' value or cumulative calculations might hinder the solution's efficiency.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Variation with different types of functions to minimize (e.g., sum, product).
arrow_right_alt
Introducing constraints on how the indices `l` and `r` are chosen (e.g., must satisfy additional conditions).
arrow_right_alt
Modifying the target to be dynamic or based on a range instead of a fixed value.

help

常见问题

外企场景

继续练习

#1649 通过指令创建有序数组 #1157 子数组中占绝大多数的元素 #2035 将数组分成两个数组并最小化数组和的差