力扣第220题“存在重复元素 III”

在本篇文章中，我们将详细解读力扣第220题“存在重复元素 III”。通过学习本篇文章，读者将掌握如何使用桶排序和滑动窗口来解决这一问题，并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释，以便于理解。

问题描述

力扣第220题“存在重复元素 III”描述如下：

给定一个整数数组，判断数组中是否存在两个不同的索引 i 和 j，使得 nums[i] 和 nums[j] 的差的绝对值最大为 t，并且 i 和 j 的差的绝对值最大为 k。

示例:
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例:
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例:
输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

解题思路

方法一：桶排序

初步分析：
- 我们可以使用桶排序的方法来解决这个问题。
- 每个桶的大小为 t + 1，这样可以确保同一个桶内的元素差值不超过 t。
- 我们使用哈希表来存储每个桶内的元素，确保窗口大小为 k。
步骤：
- 遍历数组，将元素加入对应的桶中。
- 检查同一个桶内是否存在两个元素，如果存在则返回 true。
- 检查相邻桶内是否存在元素满足条件，如果存在则返回 true。
- 如果当前窗口大小超过 k，移除最早加入的元素。

代码实现

def containsNearbyAlmostDuplicate(nums, k, t):
    if t < 0:
        return False
    
    buckets = {}
    bucket_size = t + 1

    def get_bucket_id(num):
        return num // bucket_size

    for i, num in enumerate(nums):
        bucket_id = get_bucket_id(num)

        if bucket_id in buckets:
            return True

        if bucket_id - 1 in buckets and abs(num - buckets[bucket_id - 1]) < bucket_size:
            return True

        if bucket_id + 1 in buckets and abs(num - buckets[bucket_id + 1]) < bucket_size:
            return True

        buckets[bucket_id] = num

        if i >= k:
            del buckets[get_bucket_id(nums[i - k])]

    return False

# 测试案例
print(containsNearbyAlmostDuplicate([1,2,3,1], 3, 0))  # 输出: True
print(containsNearbyAlmostDuplicate([1,0,1,1], 1, 2))  # 输出: True
print(containsNearbyAlmostDuplicate([1,5,9,1,5,9], 2, 3))  # 输出: False

方法二：滑动窗口 + 二叉搜索树

初步分析：
- 使用滑动窗口和二叉搜索树来维护当前窗口内的元素。
- 检查当前元素与窗口内元素的差值是否小于等于 t。
步骤：
- 初始化一个空的有序集合。
- 遍历数组，将当前元素加入有序集合中。
- 使用有序集合的 bisect 方法查找当前元素的邻近元素，检查是否满足条件。
- 如果窗口大小超过 k，移除最早加入的元素。

代码实现

from sortedcontainers import SortedList

def containsNearbyAlmostDuplicate(nums, k, t):
    if t < 0:
        return False

    sorted_list = SortedList()

    for i, num in enumerate(nums):
        pos = SortedList.bisect_left(sorted_list, num)
        
        if pos < len(sorted_list) and sorted_list[pos] - num <= t:
            return True
        
        if pos > 0 and num - sorted_list[pos - 1] <= t:
            return True

        sorted_list.add(num)

        if len(sorted_list) > k:
            sorted_list.remove(nums[i - k])

    return False

# 测试案例
print(containsNearbyAlmostDuplicate([1,2,3,1], 3, 0))  # 输出: True
print(containsNearbyAlmostDuplicate([1,0,1,1], 1, 2))  # 输出: True
print(containsNearbyAlmostDuplicate([1,5,9,1,5,9], 2, 3))  # 输出: False

复杂度分析

时间复杂度：
- 桶排序：O(n)，其中 n 是数组的长度。每个元素加入和移除桶的操作均为 O(1)。
- 滑动窗口 + 二叉搜索树：O(n log k)，其中 n 是数组的长度，k 是窗口大小。插入和删除操作的时间复杂度为 O(log k)。
空间复杂度：
- 桶排序：O(min(n, k))，用于存储桶内的元素。
- 滑动窗口 + 二叉搜索树：O(min(n, k))，用于存储有序集合。