LeetCode-220 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 absolute difference between nums[i] and nums[j] is at most tand the absolute difference between i and j is at most k.

题目大意

给定一个整数数组，在范围为k的区间内（i - j <= k）是否存在两个整数的差小于等于t（abs(nums[i] - nums[j] <= t)）。

示例

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

解题思路

解题思路类似于LeetCode-217和LeetCode-219，利用set作为一个记录区间为k个整数的窗口，每次只需在k个整数中进行查找，利用lower_bound可以在log(N)时间复杂度内查找到符合条件的数字。

复杂度分析

时间复杂度：O(N*log(N))

空间复杂度：O(N)

代码

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        // 注意要用long作为set类型，因为个别例子会超出int的大小范围
        set<long> win;
        for(int i = 0; i < nums.size(); ++i) {
            // 为了保证窗口set中最多只有k个整数，因此需要把范围之外的数字去掉
            if(i > k)
                win.erase(nums[i - k - 1]);
            // 利用lower_bound查找符合条件的数字
            auto iter = win.lower_bound((long)nums[i] - (long)t);
            // 若找到的数字与当前数字之差小于t则返回true
            if(iter != win.end() && *iter - nums[i] <= t)
                return true;
            win.insert(nums[i]);
        }
        
        return false;
    }
};