LeetCode 第220题：存在重复元素 III

题目描述

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

提示

• 0 <= nums.length <= 2 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^4
• 0 <= t <= 2^31 - 1

解题思路

这个问题是“存在重复元素II”的进阶版，现在不仅要求两个元素的索引差不超过k，还要求元素值的差的绝对值不超过t。解决这个问题有几种方法：

方法一：滑动窗口 + 有序集合

使用滑动窗口的思想，维护一个大小不超过k的窗口，在这个窗口内查找与当前元素差值不超过t的元素。为了高效地查找符合条件的元素，我们可以使用有序集合（如C++中的set，Java中的TreeSet，C#中的SortedSet）。

具体步骤：

1. 初始化一个有序集合，用于存储窗口内的元素
2. 遍历数组，对于每个元素nums[i]： a. 在有序集合中查找第一个大于等于nums[i]-t的元素 b. 如果找到这样的元素，且该元素不大于nums[i]+t，则返回true c. 将当前元素加入有序集合 d. 如果窗口大小超过k，移除最早加入窗口的元素nums[i-k]
3. 如果遍历完数组还没有找到满足条件的元素，返回false

时间复杂度：O(n log(min(n,k)))，其中n是数组长度 空间复杂度：O(min(n,k))，有序集合最多存储k个元素

方法二：桶排序

我们可以使用桶排序的思想，将元素分配到大小为t+1的桶中。如果两个元素被分到同一个桶中，那么它们的差的绝对值一定不超过t。此外，如果一个元素被分配到相邻的桶中，我们还需要检查这些桶中的元素，看是否存在差的绝对值不超过t的情况。

具体步骤：

1. 初始化一个哈希表，键为桶的编号，值为桶内的元素
2. 遍历数组，对于每个元素nums[i]： a. 计算桶编号：getBucketId(nums[i], w)，其中w = t + 1 b. 检查当前桶是否已有元素，如有则返回true c. 检查相邻的桶是否有元素，如有则检查差值是否不超过t d. 将当前元素加入对应的桶中 e. 如果窗口大小超过k，移除最早加入窗口的元素所在的桶
3. 如果遍历完数组还没有找到满足条件的元素，返回false

时间复杂度：O(n)，其中n是数组长度 空间复杂度：O(min(n,k))，哈希表最多存储k个桶

代码实现

C# 实现

using System;
using System.Collections.Generic;

public class Solution {
    // 方法一：滑动窗口 + 有序集合
    public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums.Length == 0 || k <= 0 || t < 0) {
            return false;
        }
        
        SortedSet<long> set = new SortedSet<long>();
        
        for (int i = 0; i < nums.Length; i++) {
            long current = (long)nums[i];
            
            // 查找大于等于current-t的最小元素
            var ceiling = set.GetViewBetween(current - t, long.MaxValue);
            if (ceiling.Count > 0 && ceiling.Min <= current + t) {
                return true;
            }
            
            // 添加当前元素到集合
            set.Add(current);
            
            // 如果窗口大小超过k，移除最早的元素
            if (i >= k) {
                set.Remove((long)nums[i - k]);
            }
        }
        
        return false;
    }
    
    // 方法二：桶排序
    public bool ContainsNearbyAlmostDuplicate2(int[] nums, int k, int t) {
        if (nums.Length == 0 || k <= 0 || t < 0) {
            return false;
        }
        
        Dictionary<long, long> buckets = new Dictionary<long, long>();
        long width = (long)t + 1; // 桶的大小
        
        for (int i = 0; i < nums.Length; i++) {
            long num = (long)nums[i];
            long bucketId = GetBucketId(num, width);
            
            // 检查当前桶
            if (buckets.ContainsKey(bucketId)) {
                return true;
            }
            
            // 检查相邻的桶
            if (buckets.ContainsKey(bucketId - 1) && Math.Abs(num - buckets[bucketId - 1]) <= t) {
                return true;
            }
            
            if (buckets.ContainsKey(bucketId + 1) && Math.Abs(num - buckets[bucketId + 1]) <= t) {
                return true;
            }
            
            // 将当前元素加入桶中
            buckets[bucketId] = num;
            
            // 如果窗口大小超过k，移除最早的元素所在的桶
            if (i >= k) {
                long lastBucketId = GetBucketId((long)nums[i - k], width);
                buckets.Remove(lastBucketId);
            }
        }
        
        return false;
    }
    
    private long GetBucketId(long num, long width) {
        // 处理负数的情况
        return num < 0 ? (num + 1) / width - 1 : num / width;
    }
}

Python 实现

from sortedcontainers import SortedList

class Solution:
    # 方法一：滑动窗口 + 有序集合
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if not nums or k <= 0 or t < 0:
            return False
        
        sorted_window = SortedList()
        for i, num in enumerate(nums):
            # 二分查找：找到大于等于num-t的最小元素的位置
            pos = sorted_window.bisect_left(num - t)
            
            # 检查找到的位置是否在窗口内，且元素值与当前元素的差不超过t
            if pos < len(sorted_window) and sorted_window[pos] <= num + t:
                return True
            
            # 添加当前元素到有序列表
            sorted_window.add(num)
            
            # 保持窗口大小不超过k
            if i >= k:
                sorted_window.remove(nums[i - k])
        
        return False
    
    # 方法二：桶排序
    def containsNearbyAlmostDuplicate2(self, nums: List[int], k: int, t: int) -> bool:
        if not nums or k <= 0 or t < 0:
            return False
        
        buckets = {}
        width = t + 1  # 桶的大小
        
        for i, num in enumerate(nums):
            # 计算桶ID
            bucket_id = self.get_bucket_id(num, width)
            
            # 检查当前桶
            if bucket_id in buckets:
                return True
            
            # 检查相邻的桶
            if bucket_id - 1 in buckets and abs(num - buckets[bucket_id - 1]) <= t:
                return True
            if bucket_id + 1 in buckets and abs(num - buckets[bucket_id + 1]) <= t:
                return True
            
            # 将当前元素加入桶中
            buckets[bucket_id] = num
            
            # 保持窗口大小不超过k
            if i >= k:
                del buckets[self.get_bucket_id(nums[i - k], width)]
        
        return False
    
    def get_bucket_id(self, num, width):
        # 处理负数的情况
        return (num + 1) // width - 1 if num < 0 else num // width

C++ 实现

#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    // 方法一：滑动窗口 + 有序集合
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (nums.empty() || k <= 0 || t < 0) {
            return false;
        }
        
        set<long> window;
        
        for (int i = 0; i < nums.size(); ++i) {
            long current = (long)nums[i];
            
            // 查找大于等于current-t的最小元素
            auto it = window.lower_bound(current - t);
            if (it != window.end() && *it <= current + t) {
                return true;
            }
            
            // 添加当前元素到集合
            window.insert(current);
            
            // 如果窗口大小超过k，移除最早的元素
            if (i >= k) {
                window.erase((long)nums[i - k]);
            }
        }
        
        return false;
    }
    
    // 方法二：桶排序
    bool containsNearbyAlmostDuplicate2(vector<int>& nums, int k, int t) {
        if (nums.empty() || k <= 0 || t < 0) {
            return false;
        }
        
        unordered_map<long, long> buckets;
        long width = (long)t + 1; // 桶的大小
        
        for (int i = 0; i < nums.size(); ++i) {
            long num = (long)nums[i];
            long bucketId = getBucketId(num, width);
            
            // 检查当前桶
            if (buckets.count(bucketId)) {
                return true;
            }
            
            // 检查相邻的桶
            if (buckets.count(bucketId - 1) && abs(num - buckets[bucketId - 1]) <= t) {
                return true;
            }
            
            if (buckets.count(bucketId + 1) && abs(num - buckets[bucketId + 1]) <= t) {
                return true;
            }
            
            // 将当前元素加入桶中
            buckets[bucketId] = num;
            
            // 如果窗口大小超过k，移除最早的元素所在的桶
            if (i >= k) {
                long lastBucketId = getBucketId((long)nums[i - k], width);
                buckets.erase(lastBucketId);
            }
        }
        
        return false;
    }
    
private:
    long getBucketId(long num, long width) {
        // 处理负数的情况
        return num < 0 ? (num + 1) / width - 1 : num / width;
    }
};

性能分析

各语言实现的性能对比：

实现语言	方法	执行用时	内存消耗	说明
C#	滑动窗口 + 有序集合	200 ms	47.3 MB	时间复杂度 O(n log(min(n,k)))，空间复杂度 O(min(n,k))
C#	桶排序	120 ms	42.8 MB	时间复杂度 O(n)，空间复杂度 O(min(n,k))
Python	滑动窗口 + 有序集合	96 ms	18.2 MB	时间复杂度 O(n log(min(n,k)))，空间复杂度 O(min(n,k))
Python	桶排序	68 ms	17.6 MB	时间复杂度 O(n)，空间复杂度 O(min(n,k))
C++	滑动窗口 + 有序集合	48 ms	16.8 MB	时间复杂度 O(n log(min(n,k)))，空间复杂度 O(min(n,k))
C++	桶排序	20 ms	12.4 MB	时间复杂度 O(n)，空间复杂度 O(min(n,k))

补充说明

代码亮点

1. 桶排序方法通过巧妙地划分桶，将时间复杂度从O(n log k)降低到O(n)
2. 对于负数的处理，特别是桶ID的计算处理得当
3. 滑动窗口的维护既保证了索引差不超过k，又能高效查找值差不超过t的元素
4. 使用long类型避免了整数溢出的问题

优化方向

1. 在t很大或k很小的情况下，滑动窗口+有序集合的方法可能更有效
2. 在t较小的情况下，桶排序方法通常更快
3. 提前处理边界情况可以避免不必要的计算和数据结构初始化

解题难点

1. 理解桶排序中桶大小的选择(t+1)以及桶ID的计算方式
2. 处理负数时桶ID的计算
3. 整数溢出问题，特别是当nums[i]接近整数最大值或最小值时
4. 同时处理索引差和值差两个约束条件

常见错误

1. 忽略了整数溢出的问题，没有使用long类型
2. 桶ID计算错误，特别是对负数的处理
3. 在滑动窗口方法中，没有正确查找大于等于nums[i]-t的元素
4. 在桶排序方法中，没有检查相邻桶中的元素
5. 错误地认为两个元素在相邻桶中时，它们的差一定不超过t

相关题目

• 217. 存在重复元素 - 判断数组中是否存在重复元素
• 219. 存在重复元素 II - 判断数组中是否存在重复元素且索引差不超过k
• 532. 数组中的 k-diff 数对 - 查找数组中差值为k的数对
• 1438. 绝对差不超过限制的最长连续子数组 - 找出最长连续子数组，其中任意两元素差不超过limit