【LeetCode每日一题】——220.存在重复元素 III

一【题目类别】

• 数组

二【题目难度】

• 困难

三【题目编号】

• 220.存在重复元素 III

四【题目描述】

• 给你一个整数数组 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<=10^5$
• $-10^9<=nums[i]<=10^9$
• $1<=indexDiff<=nums.length$
• $0<=valueDiff<=10^9$

七【解题思路】

• 本题如果使用暴力方法很明显会超时，所以我们利用哈希表来完成桶排序：
  • 桶排序思想：将元素按值划分到不同的桶中，确保同一桶内的元素值差不超过 valueDiff。
  • 桶大小：每个桶的大小设置为 valueDiff + 1。
  • 桶ID计算：通过 x / (valueDiff + 1) 来计算元素 x 所属的桶ID。
  • 相邻桶检查：检查当前桶以及相邻桶内的元素，保证值差不超过 valueDiff。
  • 索引范围检查：确保当前元素与桶内其他元素的索引差不超过 indexDiff，超出范围则删除过期元素。
• 最后返回结果即可
• 具体细节可以参考下面的代码

八【时空频度】

• 时间复杂度：$O(n)$，$n$为传入的数组的长度
• 空间复杂度：$O(n)$，$n$为传入的数组的长度

九【代码实现】

1. Java语言版

class Solution {// 根据给定的valueDiff计算当前值x所在的区间IDprivate long getId(long x, long valueDiff) {if (x >= 0) {// 正数的区间ID为x / (valueDiff + 1)return x / (valueDiff + 1);} else {// 负数的区间ID为(x + 1) / (valueDiff + 1) - 1，处理负数时偏移1以保证负数的ID正确return (x + 1) / (valueDiff + 1) - 1;}}// 判断是否存在两个元素，其索引差小于等于indexDiff，值的差小于等于valueDiffpublic boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {int n = nums.length;Map<Long, Long> map = new HashMap<>();// 哈希表用于存储每个区间ID对应的最新元素值// 遍历数组中的每个元素for (int i = 0; i < n; i++) {long x = nums[i];   // 当前元素值long id = getId(x, valueDiff);  // 获取当前元素所属的区间ID// 如果当前元素的索引超出范围，移除之前索引差超过indexDiff的元素if (i - (indexDiff + 1) >= 0) {map.remove(getId(nums[i - (indexDiff + 1)], valueDiff));}// 检查当前区间ID是否已经存在相同的元素，若存在则返回trueif (map.containsKey(id)) {return true;}// 检查相邻的区间ID是否存在符合条件的元素// 区间ID为id-1，若存在并且两者差值小于等于valueDiff，则符合条件if (map.containsKey(id - 1) && Math.abs(map.get(id - 1) - x) <= valueDiff) {return true;}// 区间ID为id+1，若存在并且两者差值小于等于valueDiff，则符合条件if (map.containsKey(id + 1) && Math.abs(map.get(id + 1) - x) <= valueDiff) {return true;}// 如果都没有找到符合条件的元素，则将当前元素放入哈希表map.put(id, x);}// 如果没有找到符合条件的元素，返回falsereturn false;}
}

2. Python语言版

class Solution:# 根据给定的valueDiff计算当前值x所在的区间IDdef get_id(self, x, valueDiff):if x >= 0:# 正数的区间ID为x / (valueDiff + 1)return x // (valueDiff + 1)else:# 负数的区间ID为(x + 1) / (valueDiff + 1) - 1，处理负数时偏移1以保证负数的ID正确return (x + 1) // (valueDiff + 1) - 1# 判断是否存在两个元素，其索引差小于等于indexDiff，值的差小于等于valueDiffdef containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:n = len(nums)map = {}    # 哈希表用于存储每个区间ID对应的最新元素值# 遍历数组中的每个元素for i in range(n):x = nums[i] # 当前元素值id = self.get_id(x, valueDiff)  # 获取当前元素所属的区间ID# 如果当前元素的索引超出范围，移除之前索引差超过indexDiff的元素if i - (indexDiff + 1) >= 0:del map[self.get_id(nums[i - (indexDiff + 1)], valueDiff)]# 检查当前区间ID是否已经存在相同的元素，若存在则返回Trueif id in map:return True# 检查相邻的区间ID是否存在符合条件的元素# 区间ID为id-1，若存在并且两者差值小于等于valueDiff，则符合条件if (id - 1) in map and abs(map[id - 1] - x) <= valueDiff:return True# 区间ID为id+1，若存在并且两者差值小于等于valueDiff，则符合条件if (id + 1) in map and abs(map[id + 1] - x) <= valueDiff:return True# 如果都没有找到符合条件的元素，则将当前元素放入哈希表map[id] = x# 如果没有找到符合条件的元素，返回Falsereturn False

3. C++语言版

class Solution {
public:// 根据给定的valueDiff计算当前值x所在的区间IDlong getId(long x, long valueDiff) {if (x >= 0) {// 正数的区间ID为x / (valueDiff + 1)return x / (valueDiff + 1);} else {// 负数的区间ID为(x + 1) / (valueDiff + 1) - 1，处理负数时偏移1以保证负数的ID正确return (x + 1) / (valueDiff + 1) - 1;}}// 判断是否存在两个元素，其索引差小于等于indexDiff，值的差小于等于valueDiffbool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {int n = nums.size();unordered_map<int, int> map;  // 哈希表用于存储每个区间ID对应的最新元素值// 遍历数组中的每个元素for (int i = 0; i < n; i++) {long x = nums[i];  // 当前元素值long id = getId(x, valueDiff);  // 获取当前元素所属的区间ID// 如果当前元素的索引超出范围，移除之前索引差超过indexDiff的元素if (i - (indexDiff + 1) >= 0) {map.erase(getId(nums[i - (indexDiff + 1)], valueDiff));}// 检查当前区间ID是否已经存在相同的元素，若存在则返回trueif (map.find(id) != map.end()) {return true;}// 检查相邻的区间ID是否存在符合条件的元素// 区间ID为id-1，若存在并且两者差值小于等于valueDiff，则符合条件if (map.find(id - 1) != map.end() && abs(map[id - 1] - x) <= valueDiff) {return true;}// 区间ID为id+1，若存在并且两者差值小于等于valueDiff，则符合条件if (map.find(id + 1) != map.end() && abs(map[id + 1] - x) <= valueDiff) {return true;}// 如果都没有找到符合条件的元素，则将当前元素放入哈希表map[id] = x;}// 如果没有找到符合条件的元素，返回falsereturn false;}
};

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C++语言版