題目鏈接
tag:
- Medium贬媒；
question：
??Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
思路：
??這道題跟之前兩道Contains Duplicate 存在重復(fù)值和Contains Duplicate II 存在重復(fù)值 ||的關(guān)聯(lián)并不大，前兩道起碼跟重復(fù)值有關(guān)委煤，這道題的焦點(diǎn)不是在重復(fù)值上面绷蹲，反而是關(guān)注與不同的值之間的關(guān)系棒卷，這里有兩個(gè)限制條件，兩個(gè)數(shù)字的坐標(biāo)差不能大于k瘸右，值差不能大于t娇跟。
??這道題如果用brute force會(huì)超時(shí)，所以我們只能另辟蹊徑太颤。這里我們使用map數(shù)據(jù)結(jié)構(gòu)來(lái)解苞俘，用來(lái)記錄數(shù)字和其下標(biāo)之間的映射。 這里需要兩個(gè)指針i和j龄章，剛開始i和j都指向0吃谣，然后i開始向右走遍歷數(shù)組，如果i和j之差大于k做裙，且m中有nums[j]岗憋，則刪除并j加一。這樣保證了m中所有的數(shù)的下標(biāo)之差都不大于k锚贱，然后我們用map數(shù)據(jù)結(jié)構(gòu)的lower_bound()函數(shù)來(lái)找一個(gè)特定范圍仔戈，就是大于或等于nums[i] - t的地方，所有小于這個(gè)閾值的數(shù)和nums[i]的差的絕對(duì)值會(huì)大于t。然后檢測(cè)后面的所有的數(shù)字监徘，如果數(shù)的差的絕對(duì)值小于等于t晋修，則返回true。最后遍歷完整個(gè)數(shù)組返回false凰盔。代碼如下：
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
map<long long, int> m;
int j = 0;
for (int i=0; i<nums.size(); ++i) {
if (i - j > k)
m.erase(nums[j++]);
auto a = m.lower_bound((long long)nums[i] - t);
if (a != m.end() && abs(a->first - nums[i]) <= t)
return true;
m[nums[i]] = i;
}
return false;
}
};
