Leetcode 220 Contains Duplicate III

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;       
    }
};