Hard

题目描述

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff。

找到一对下标 (i, j)，满足：

  • i != j
  • abs(i - j) <= indexDiff
  • abs(nums[i] - nums[j]) <= valueDiff

如果存在这样的下标对，返回 true；否则，返回 false。

示例 1：

输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
输出：true
解释：我们可以选择 (i, j) = (0, 3)。
我们满足三个条件：
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

示例 2：

输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
输出：false
解释：尝试了所有可能的下标对 (i, j) 后，都无法满足这三个条件，所以返回 false。

提示：

  • 2 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 1 <= indexDiff <= nums.length
  • 0 <= valueDiff <= 10^9

解题思路

这道题需要在数组中找到满足下标差和值差都在指定范围内的数字对。

主要思路：

  1. 滑动窗口 + 有序集合：维护一个大小为 indexDiff + 1 的滑动窗口，窗口内的元素按值排序。对于当前元素，在窗口中查找是否存在与其值差不超过 valueDiff 的元素。

  2. 桶排序思想：将数值范围划分为大小为 valueDiff + 1 的桶，相同桶内的任意两元素值差必定 ≤ valueDiff，相邻桶的元素也可能满足条件。

  3. 暴力法：对每个位置，检查其后 indexDiff 个位置的元素，时间复杂度 O(n × indexDiff)，不够优化。

推荐解法：滑动窗口 + 有序集合 使用 TreeSet/set 维护窗口内元素，利用二分查找快速定位可能满足条件的元素。通过 lower_bound 找到第一个 ≥ nums[i] - valueDiff 的元素，检查是否 ≤ nums[i] + valueDiff。

这种方法时间复杂度 O(n log k)，其中 k = indexDiff + 1，空间复杂度 O(k)，是最优解法。

代码实现

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        set<long long> window;
        
        for (int i = 0; i < nums.size(); i++) {
            // 查找是否存在满足条件的元素
            auto it = window.lower_bound((long long)nums[i] - valueDiff);
            if (it != window.end() && *it <= (long long)nums[i] + valueDiff) {
                return true;
            }
            
            // 将当前元素加入窗口
            window.insert(nums[i]);
            
            // 维护窗口大小
            if (window.size() > indexDiff) {
                window.erase(nums[i - indexDiff]);
            }
        }
        
        return false;
    }
};

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        from sortedcontainers import SortedList
        
        window = SortedList()
        
        for i, num in enumerate(nums):
            # 查找是否存在满足条件的元素
            idx = window.bisect_left(num - valueDiff)
            if idx < len(window) and window[idx] <= num + valueDiff:
                return True
            
            # 将当前元素加入窗口
            window.add(num)
            
            # 维护窗口大小
            if len(window) > indexDiff:
                window.remove(nums[i - indexDiff])
        
        return False

public class Solution {
    public bool ContainsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        var window = new SortedSet<long>();
        
        for (int i = 0; i < nums.Length; i++) {
            long num = nums[i];
            
            // 查找是否存在满足条件的元素
            var view = window.GetViewBetween(num - valueDiff, num + valueDiff);
            if (view.Count > 0) {
                return true;
            }
            
            // 将当前元素加入窗口
            window.Add(num);
            
            // 维护窗口大小
            if (window.Count > indexDiff) {
                window.Remove(nums[i - indexDiff]);
            }
        }
        
        return false;
    }
}

var containsNearbyAlmostDuplicate = function(nums, indexDiff, valueDiff) {
    const window = [];
    
    for (let i = 0; i < nums.length; i++) {
        // 在有序数组中二分查找
        const target = nums[i];
        let left = 0, right = window.length;
        
        // 找到第一个 >= target - valueDiff 的位置
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (window[mid] < target - valueDiff) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 检查是否存在满足条件的元素
        if (left < window.length && window[left] <= target + valueDiff) {
            return true;
        }
        
        // 插入当前元素保持有序
        window.splice(left, 0, target);
        
        // 维护窗口大小
        if (window.length > indexDiff) {
            const removeVal = nums[i - indexDiff];
            const removeIdx = window.indexOf(removeVal);
            window.splice(removeIdx, 1);
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
滑动窗口 + 有序集合O(n log k)O(k)
桶排序O(n)O(k)
暴力法O(n × indexDiff)O(1)

其中 n 为数组长度，k = indexDiff + 1 为窗口大小。推荐使用滑动窗口 + 有序集合的解法。

相关题目