題目： LeetCode - 220. Contains Duplicate III

題目說明

給一個陣列，求對於陣列中的某個元素的左右各 k 個元素中是否存在兩者的差小於等於 t 的元素。

解題思路

為了計算方便，我們先確定 j 的位置，之後再往前找 i，最簡單的方法為兩個迴圈，但是這樣會超時，所以必須使用二分搜尋，這裡我們使用 lower_bound() 這個函式達成二分搜尋的效果，使用 Multiset 紀錄前面 k 個元素，之後使用此函式找到第一個大於等於 nums[j] - t 的值，若有找到並且這個值會小於等於 nums[j] + t，表示兩者的差會小於等於 t，回傳 True。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
    {
        multiset<long> ms;
        for(int j = 0; j < nums.size(); ++j)
        {
            if(j > k) ms.erase(ms.lower_bound(nums[j - k - 1]));
            auto iter = ms.lower_bound(long(nums[j]) - long(t));
            if(iter != ms.end() && *iter <= long(nums[j]) + long(t)) return true;
            ms.insert(nums[j]);
        }
        return false;
    }
};