Leetcode 220 Contains Duplicate III

1. 问题描述

　　给定一个整数数组nums[]，查找是否存在两个下标i和j，满足 |numsi?numsj|≤t 且 |i?j|≤k 。

2. 方法与思路

　　总得思路就是：“滑动窗口”+unordered_map。
　　推理过程如下：
　　 |numsi?numsj|≤t?|numsi/t?numsj/t|≤1 ；
　　由上式可以推出： |?numsi/t???numsj/t?|≤1
　　等价于： ?numsi/t?∈{?numsj/t?,?numsj/t??1,?numsj/t?+1} 。
　　我们只需要维持一个大小为K的窗口，键值为 ?numsi/t? , 值为 numsi 。然后循环遍历nums[]数组，与unordered_ map中键集对应的值进行差得绝对值运算，再判断即可。
　　对于STL中关于unordered_map的相关可参考官方References 对unordered_map讲解。

注意： unordered_map是一种特殊的hash map，它不按照键值进行排序。通过hash表的算法，查找效率为O(1)。但会消耗一定内存。进行差值运算时需转换为long类型，否则会溢出。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector
   
    & nums, int k, int t) { if(t < 0 | k <1) return false; int i,key; unordered_map
    
      dict; for(i =0; i < nums.size(); i++) { key = nums[i]/max(1,t); //map
     
      ::iterator it; if( (dict.find(key) != dict.end() && abs(nums[i] - dict[key]) <= t) || (dict.find(key-1) != dict.end() && abs((long)nums[i] - (long)dict[key-1]) <= t) || (dict.find(key+1) !=dict.end() && abs(nums[i] - dict[key+1]) <= t)) { return true; } //dict[key] = nums[i]; dict.insert(pair
      
       (key,nums[i])); if(i >= k) { dict.erase(nums[i-k]/max(1,t)); //删除窗口大小之外的键值 } } return false; } };