Hard

题目描述

温斯顿得到了上述神秘函数 func。他有一个整数数组 arr 和一个整数 target，他想找到使得 |func(arr, l, r) - target| 尽可能小的 l 和 r 值。

返回 |func(arr, l, r) - target| 的最小可能值。

注意 func 应该在满足 0 <= l, r < arr.length 的 l 和 r 值下调用。

示例 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]] 调用 func，温斯顿得到结果 [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
解释：温斯顿对所有可能的 [l,r] 值调用 func，总是得到 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[i…j] 的 AND 值 ≥ 子数组 arr[i…j+1] 的 AND 值
  • 对于每个索引 i，使用二分搜索或三分搜索找到索引 j，使得 |target - AND(arr[i…j])| 最小，用这个值更新全局答案。

解题思路

这道题的核心是理解位运算 AND 操作的单调性质：随着子数组长度增加，AND 值只会减少或保持不变。

关键观察：

  1. 对于固定的左端点 i，右端点 j 向右扩展时，AND(arr[i..j]) 单调递减
  2. 这意味着对于每个起始位置 i，所有可能的 AND 值构成一个递减序列
  3. 由于数组元素最大为 10^6（约20位），每个位置最多产生20个不同的 AND 值

算法思路： 我们可以用集合来维护所有可能的 AND 值。遍历数组时：

  • 对于当前元素 arr[i]，更新之前所有可能的 AND 值
  • 将当前元素本身也加入候选集合
  • 用新的 AND 值集合更新全局最小差值

优化点：

  • 使用集合去重，避免重复计算相同的 AND 值
  • 利用 AND 操作的单调性，每次最多产生有限个不同值

这种方法的时间复杂度实际上是 O(n log(max_val))，因为每个位置最多产生 log(max_val) 个不同的 AND 值。

代码实现

class Solution {
public:
    int closestToTarget(vector<int>& arr, int target) {
        set<int> candidates;
        int result = INT_MAX;
        
        for (int num : arr) {
            set<int> newCandidates;
            newCandidates.insert(num);
            
            for (int candidate : candidates) {
                newCandidates.insert(candidate & num);
            }
            
            for (int candidate : newCandidates) {
                result = min(result, abs(candidate - target));
            }
            
            candidates = newCandidates;
        }
        
        return result;
    }
};

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        candidates = set()
        result = float('inf')
        
        for num in arr:
            new_candidates = {num}
            
            for candidate in candidates:
                new_candidates.add(candidate & num)
            
            for candidate in new_candidates:
                result = min(result, abs(candidate - target))
            
            candidates = new_candidates
        
        return result

public class Solution {
    public int ClosestToTarget(int[] arr, int target) {
        HashSet<int> candidates = new HashSet<int>();
        int result = int.MaxValue;
        
        foreach (int num in arr) {
            HashSet<int> newCandidates = new HashSet<int>();
            newCandidates.Add(num);
            
            foreach (int candidate in candidates) {
                newCandidates.Add(candidate & num);
            }
            
            foreach (int candidate in newCandidates) {
                result = Math.Min(result, Math.Abs(candidate - target));
            }
            
            candidates = newCandidates;
        }
        
        return result;
    }
}

var closestToTarget = function(arr, target) {
    let candidates = new Set();
    let result = Infinity;
    
    for (let num of arr) {
        let newCandidates = new Set();
        newCandidates.add(num);
        
        for (let candidate of candidates) {
            newCandidates.add(candidate & num);
        }
        
        for (let candidate of newCandidates) {
            result = Math.min(result, Math.abs(candidate - target));
        }
        
        candidates = newCandidates;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log(max_val))n 为数组长度，max_val 为数组元素最大值，每个位置最多产生 log(max_val) 个不同的 AND 值
空间复杂度O(log(max_val))集合中最多存储 log(max_val) 个不同的 AND 值