因为要考虑超时问题，所以虽然简单的for循环也可以做，但是要用map等内部红黑树实现的容器。
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.
|nums[i] - nums[j]| <= t
|i - j| <= k
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
//nums[i] and nums[j] is at most t
//i and j is at most k
/*
//两个for循环是超时的………………必须把O(n*n)变成O(n*logn)
int len = nums.size();
if (len==0 || len==1 || k<0 || t<0)
return false;
for (int i=0;i<len;i++){
for (int j=i+1;j<len && j<=i+k;j++){
if (abs((long)nums[i]-(long)nums[j])<=t)
return true;
}
}
return false;
*/
//这个实现是能找到的写的最简单的_(¦3」∠)_
map<long, int> m;
int j = ;
for (int i = ; i < nums.size(); ++i) {
if (i - j > k && m[nums[j]] == j)
m.erase(nums[j++]);
auto a = m.lower_bound((long)nums[i] - t);
if (a != m.end() && abs(a->first - nums[i]) <= t)
return true;
m[nums[i]] = i;
}
return false;
}
};
唉…感觉一遇到难的题，就变成答案的搬运工…还是要努力呐
题目大意：给一个整数数组，找到是否存在两个不同的下标i和j，使得nums[i]和nums[j]的差的绝对值不超过t并且i和j的差的绝对值不超过k
分析：
建立一个map，对应的是元素的值到元素的下标的映射。
指针i将nums数组从头遍历到尾，j指针一开始指向0。i向右走的时候如果i和j之差大于k，且m中有nums[j]，就将nums[j]从m中移除，且j向前走一步。这样就保证了m中所有的元素满足第一个条件：i和j的差的绝对值不超过k
接下来考虑nums[i]和nums[j]的差的绝对值不超过t，abs(num[i] – nums[j]) <= t 则 nums[j]的最小可能满足条件的值为>=nums[i] – t的，所以使用map中的lower_bound，寻找第一个大于等于nums[i] – t的地方，找到后标记为a，此时的a只是取到了可能满足的最小的a，但(a – nums[i])不一定满足，所以检验a是否存在于map中且是否abs(a->first – nums[i]) <= t。如果都满足说明可以return true
为什么要循环的最后写map的插入呢，因为比较的是i之前的所有元素。为了防止找到的是nums[i]本身，然后让nums[i]自己本身和自己比较差值了，这样结果就不对了。
如果到最后都没有能够return true，则return false
语法上可以学习的点：
对于auto而言（C++11新特性！！），其在于type deduce，那么第一点，它不会允许没有初始化值的声明，如：
int x;
auto y; // error
aoto可以节省很多的字，比如容器的iterator：
vector <int> v;
vector <int> ::iterator iter = v.begin(); //第一种写法
auto I = v.begin(); //第二种写法
关于auto的讨论：https://www.zhihu.com/question/35517805
关于C++11的新特性：https://www.cnblogs.com/feng-sc/p/5710724.html