220.存在重复元素③

一、题目

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。

找出满足下述条件的下标对 (i, j)：

i != j,
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff
如果存在，返回 true ；否则，返回 false 。

二、思路

就是滑动窗口，比较窗口内的规则。

class Solution {
public:bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {int i=0,j=1;int n=nums.size();while(i<n){j=i+1;while(j<n){if(abs(j-i)>indexDiff){break;}if(abs(nums[i]-nums[j])<=valueDiff){return true;}j++;}i++;}return false;}
};

卡在第44个用例了

发现少了一个j=i+1

两个while的结构好像时间复杂度很高

三、解法

class Solution {
public:bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {int n = nums.size();set<int> rec;for (int i = 0; i < n; i++) {auto iter = rec.lower_bound(max(nums[i], INT_MIN + t) - t);if (iter != rec.end() && *iter <= min(nums[i], INT_MAX - t) + t) {return true;}rec.insert(nums[i]);if (i >= k) {rec.erase(nums[i - k]);}}return false;}
};作者：力扣官方题解
链接：https://leetcode.cn/problems/contains-duplicate-iii/solutions/726619/cun-zai-zhong-fu-yuan-su-iii-by-leetcode-bbkt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

四、收获

是我了

一般超时的问题，基本就是查找时候时间复杂度太高了，要用二分查找
滑动窗口可以用队列的数据结构来维护。