题目
给你一个整数数组 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
滑动窗口+有序集合
代码
class Solution { public: bool containsNearbyAlmostDuplicate(vector& nums, int indexDiff, int valueDiff) { std::multiset setHas; for (int i = 0; i < nums.size(); i++) { const int iDelIndex = i - indexDiff - 1; if (iDelIndex >= 0) { auto it = setHas.find(nums[iDelIndex]); setHas.erase(it); } auto it1 = setHas.lower_bound(nums[i] - valueDiff); auto it2 = setHas.upper_bound(nums[i] + valueDiff); if (it1 != it2) { return true; } setHas.emplace(nums[i]); } return false; } };
分析
如果(i,j)符合，则(j,i)也符合。所以可以只考虑i<j，不考虑i>j。题意明确表示i!=j。所以只需要考虑i<j。用有序集合表示滑动窗口nums[max(0,j-k),j]。其实用set就可以了，multiset可以少一个判断：如果存在重复值直接返回true。
桶排序
用桶来表示滑动窗口。设置桶的大小为valueDiff+1，如果2个数在同一个桶中说明符合。如果符合直接返回，所以一个桶不会存在两个像素。可以用哈希映射来表示桶。如果不在一个桶，还要比较是否和前一个桶或后一桶符合条件。
代码
class Solution { public: bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) { unordered_map<int, int> mp; int n = nums.size(); for (int i = 0; i < n; i++) { const int curValue = nums[i]; int inx = GetBucketIndex(curValue, t + 1); if (mp.count(inx)) { return true; } if (mp.count(inx - 1) && (abs(curValue - mp[inx - 1]) <= t)) { return true; } if (mp.count(inx + 1) && (abs(curValue - mp[inx + 1]) <= t)) { return true; } mp[inx] = curValue; if (i>= k) { const int iEraseIndex = GetBucketIndex(nums[i - k ],t+1); mp.erase(iEraseIndex); } } return false; } int GetBucketIndex(int value, int iBuckCap) { return value >= 0 ? (value / iBuckCap) : ((value + 1) / iBuckCap - 1); } };
其它
视频课程
要是你认为本篇难道较大，不好入手，推荐你先学习基础算法的课程，我已完成部分，余下部分持续更新中，就在CSDN学院。
https://edu.csdn.net/course/detail/38771
C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 **C+
+17**
相关下载
如果你想观其大略，建设下载《闻缺陷则喜算法册》doc版
