220 存在重复元素 III

本文最后更新于：2021年1月20日 下午

在整数数组 nums 中，是否存在两个下标 i\ 和 j\，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i\ 和 j\ 的差的绝对值也小于等于 ķ 。

如果存在则返回 true，不存在返回 false。

示例 1:

1
2
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true

示例 2:

1
2
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true

示例 3:

1
2
输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

Solution

  • 使用范围查找，超时

Testcase

1
2
3
[2147483647,-1,2147483647]
1
2147483647
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// @lc code=start
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(nums.size()<=1) return false;
        if(k<=0) return false;
        unordered_set<long long> record;
        for(int i=0; i<nums.size(); ++i){
            for(long long j=(long long)nums[i]-t; j<=(long long)nums[i]+t; ++j){
                if(record.find(j) != record.end())
                    return true;
            }
            record.insert((long long)nums[i]);
            if(record.size()==k+1)
                record.erase((long long)nums[i-k]);
        }
        return false;
    }
};
// @lc code=end
  • 这一题是在考整型溢出。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// @lc code=start
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(nums.size()<=1) return false;
        if(k<=0) return false;
        set<long long> record;
        for(int i=0; i<nums.size(); ++i){
            if(record.lower_bound((long long)nums[i] - (long long)t) != record.end()
                && *record.lower_bound((long long)nums[i]-(long long)t) <= (long long) nums[i] + (long long)t)
                return true;
            record.insert(nums[i]);
            if(record.size()==k+1)
                record.erase(nums[i-k]);
        }
        return false;
    }
};
// @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！