220. Contains Duplicate III

发表于 | 更新于: | 分类于 | | 阅读次数:

Problem

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 t and the absolute difference between i and j is at most k.

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

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

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

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

Solution

Analysis

The first idea came in my mind is the bruce method.Computing every candidate in nums[i] and nums[j], i and j. If the condition is met, return true; if every candidate is false, then return false. But the shortcoming of this solution is that the time-consuming is very high, Can’t pass all test cases.

After analysis, two indices i and j, the condition is : |nums[i] – nums[j]|<= t && | i – j | <=k. We can maintain a window that does not exceed size k. According the size, the condition about index is met. So the main problem is the value limit. The current value nums[i], a value in the window x, then, -t <= x-nums[i] <= t, nums[i]-t <= x <= nums[i] + t. So we can judge the result by finding whether there is a element in the window meeting the condition.

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef long long LL;
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t){ 
        if (nums.empty() || k <= 0 || t < 0) return false;
        
        set<LL> order;
        
        for (int i=0; i< nums.size(); ++i){
            //返回第一个大于等于val元素的iterator(下标)
            auto it = order.lower_bound((LL)nums[i] - (LL)t);
            
            if (it != order.end() && *it <= (LL)nums[i] + (LL)t)
                return true;
            
            if (i >= k) order.erase(nums[i-k]);
            order.insert(nums[i]);
        }
        return false;
    }
};
您的支持就是我更新的最大动力!谢谢!