[LeetCode] Contains Duplicate III

[LeetCode] Contains Duplicate III

 

Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

解題思路：

給定一個整數數組，判斷其中是否存在兩個不同的下標i和j滿足：| nums[i] - nums[j] | <= t 並且 | i - j | <= k。

 

如果： | nums[i] - nums[j] | <= t   式a

等價： | nums[i] / t - nums[j] / t | <= 1   式b

推出： | floor(nums[i] / t) - floor(nums[j] / t) | <= 1   式c

?等價： floor(nums[j] / t) ∈ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 式d

其中式b是式c的充分非必要條件，因為逆否命題與原命題等價，所以：

如果： floor(nums[j] / t) ? {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 非d

推出： | nums[i] - nums[j] | > t   非a

用一個hash表來存儲滑動窗口的數值，其中鍵值為nums[i]/t，對於數值nums[k]，若存在鍵為nums[k]/t，nums[k]/t-1，nums[k]/t+1，再比較他們的數值。

 

有兩個地方需要注意：

1、該題目可能會int類型溢出，因此需要先轉化成long long類型。

2、map和unordered_map並不是按插入順序排序的。因此還需要用一個隊列來維持一個滑動窗口。

下面是C++代碼：

 

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {
        if(k<1||t<0){
            return false;
        }
        unordered_map nums_map;
        queue keys;     //順序存儲的一些鍵值
        int len = nums.size();
        for(int i=0; ik){
                nums_map.erase(keys.front());
                keys.pop();
            }
        }
        return false;
    }
};

 

參考鏈接：http://bookshadow.com/weblog/2015/06/03/leetcode-contains-duplicate-iii/