ip库网站源码,时间轴 网站模板,商城网站怎么做的,php做图片交互网站代码目录 一、题目二、思路三、解法四、收获 一、题目
给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。
找出满足下述条件的下标对 (i, j)#xff1a;
i ! j, abs(i - j) indexDiff abs(nums[i] - nums[j]) valueDiff 如果存在#xff0c;返回 true
i ! j, abs(i - j) indexDiff abs(nums[i] - nums[j]) valueDiff 如果存在返回 true 否则返回 false 。
二、思路
就是滑动窗口比较窗口内的规则。
class Solution {
public:bool containsNearbyAlmostDuplicate(vectorint nums, int indexDiff, int valueDiff) {int i0,j1;int nnums.size();while(in){ji1;while(jn){if(abs(j-i)indexDiff){break;}if(abs(nums[i]-nums[j])valueDiff){return true;}j;}i;}return false;}
};卡在第44个用例了 发现少了一个ji1 两个while的结构好像时间复杂度很高
三、解法
class Solution {
public:bool containsNearbyAlmostDuplicate(vectorint nums, int k, int t) {int n nums.size();setint 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
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。四、收获
是我了 一般超时的问题基本就是查找时候时间复杂度太高了要用二分查找 滑动窗口可以用队列的数据结构来维护。
