存在重复元素 III

标签: 数组 桶排序 有序集合 排序 滑动窗口

难度: 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) 。
满足下述 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) ，均无法满足这 3 个条件，因此返回 false 。

提示：

  • 2 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 1 <= indexDiff <= nums.length
  • 0 <= valueDiff <= 109

Submission

运行时间: 83 ms

内存: 33.1 MB

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        if valueDiff == 0 and len(nums) == len(set(nums)):
            return False
        if indexDiff == 0 or valueDiff < 0:
            return False
        bucket = {}
        n = len(nums)
        for i in range(n):
            m = nums[i] // (valueDiff + 1)
            if m in bucket:
                return True
            if m - 1 in bucket:
                if nums[i] - bucket[m - 1] <= valueDiff:
                    return True
            if m + 1 in bucket:
                if bucket[m + 1] - nums[i] <= valueDiff:
                    return True
            if i >= indexDiff:
                del bucket[nums[i - indexDiff] // (valueDiff + 1)]
            bucket[m] = nums[i]
        return False

Explain

该题解使用了桶排序的思想。将数组按照 valueDiff 进行分桶，每个桶的大小为 valueDiff+1。对于每个元素，检查其所在的桶以及相邻的两个桶内是否存在满足条件的元素。如果找到了这样的元素对，就返回 True。为了满足 indexDiff 的限制，使用一个哈希表 bucket 来维护一个大小为 indexDiff 的滑动窗口，并在窗口滑动时及时删除旧桶。

时间复杂度: O(n)

空间复杂度: O(min(n, indexDiff))

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        # 特殊情况处理
        if valueDiff == 0 and len(nums) == len(set(nums)):
            return False
        if indexDiff == 0 or valueDiff < 0:
            return False
        
        bucket = {}
        n = len(nums)
        
        for i in range(n):
            # 计算当前元素所在的桶的索引
            m = nums[i] // (valueDiff + 1)
            
            # 检查当前桶是否存在元素
            if m in bucket:
                return True
            
            # 检查相邻的桶是否存在满足条件的元素
            if m - 1 in bucket:
                if nums[i] - bucket[m - 1] <= valueDiff:
                    return True
            if m + 1 in bucket:
                if bucket[m + 1] - nums[i] <= valueDiff:
                    return True
            
            # 维护一个大小为 indexDiff 的滑动窗口
            if i >= indexDiff:
                del bucket[nums[i - indexDiff] // (valueDiff + 1)]
            
            # 将当前元素加入哈希表
            bucket[m] = nums[i]
        
        return False

Explore

在桶排序的思想中，选择桶的大小为valueDiff+1是为了确保同一个桶中的任何两个元素之间的差值最大为valueDiff。这是因为如果两个元素的差值小于或等于valueDiff，它们除以valueDiff+1的结果将落在同一个桶中。此外，这种设置还避免了跨多个桶进行复杂的比较，如果桶的大小小于valueDiff+1，则可能需要检查更多相邻桶，增加复杂度。这样的设置简化了问题，使得只需要检查元素所在桶及其最多两个相邻桶。

题解中通过维护一个大小为indexDiff的滑动窗口来确保比较的元素满足indexDiff条件。具体来说，当遍历到新的元素时，如果其索引超出了当前窗口的范围（即大于等于indexDiff），则从哈希表中删除最早进入窗口的元素所在的桶。这样可以保证在哈希表中的任何元素都是距离当前元素索引差不超过indexDiff的元素。因此，即便检查相邻桶，也只会比较满足indexDiff条件的元素。

虽然在indexDiff非常小的情况下，可能会出现删除后立即需要该桶数据的情况，但这种情况下仍需删除元素以保证每个元素与比较元素的索引差不超过indexDiff。这种删除策略是为了保证哈希表中仅包含滑动窗口内的元素，避免不符合条件的比较。虽然不是所有情况下都是最优的（如频繁的插入和删除操作可能导致效率低下），但它确保了算法的正确性和简化了实现。对于更优化的策略，可能需要根据具体的使用场景和性能测试结果来调整。

当valueDiff为0时，题目要求的是数组中是否存在两个不同位置的元素值完全相同。如果数组中无重复元素（即所有元素都是唯一的），显然不可能找到两个值完全相同的元素。因此，在valueDiff为0且数组中无重复元素的情况下，直接返回False是正确的，因为不存在任何符合条件的元素对。这种处理有效地减少了不必要的计算，优化了算法性能。