专栏首页计算机视觉与深度学习基础Leetcode 220. Contains Duplicate III

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

219的再升级版,不但要求下标差的绝对值不超过k,还要求数值差的绝对值不超过t。

最外层遍历数组,对于每一个位置,我们需要知道它前k个位置中和它在数值上最接近的位置,显然要用到搜索树。

不需要手写,因为set就是搜索树的一种实现。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, long long t) {
        set<long long> s;
        for(int i = 0; i < nums.size(); i++)
        {
            if(i > k) s.erase(nums[i - k - 1]);//删除前面第k+1个元素
            set<long long>::iterator pos = s.lower_bound(nums[i] - t);//如果*pos >= nums[i] - t,则*pos - nums[i] >= -t
            if(pos != s.end() && *pos - nums[i] <= t) return true; //存在*pos,且满足上界条件
            s.insert(nums[i]);
        }
        return false;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 26 Remove Duplicates from Sorted Array

    Given a sorted array, remove the duplicates in place such that each element app...

    triplebee
  • Leetcode 31 Next Permutation

    Implement next permutation, which rearranges numbers into the lexicographically...

    triplebee
  • Leetcode 189 Rotate Array

    Rotate an array of n elements to the right by k steps. For example, with n = 7...

    triplebee
  • 2019 第十届蓝桥杯C/C++ 省赛B组题解

    又是一年一度的蓝桥杯,这次也应该是我大学最后一次学科竞赛了,今年的省赛题型和往届有些不同,代码填空没有了,只有结果填空和编程大题,不过坑还是一样的多,稍不注意就...

    指点
  • leetcode第一天

    leetcode 第一天 2017年12月24日 第一次刷leetcode真的是好慢啊,三道题用了三个小时,而且都是简单题。 数组 1.(674)Longe...

    郭耀华
  • 【leetcode刷题】T162-打家劫舍 II

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有...

    木又AI帮
  • LeetCode 53.最大子序列和 - JavaScript

    题目描述:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    心谭博客
  • Array - 53. Maximum Subarray

    Given an integer array nums, find the contiguous subarray (containing at least o...

    用户5705150
  • LeetCode 368. 最大整除子集(DP)

    给出一个由无重复的正整数组成的集合,找出其中最大的整除子集,子集中任意一对 (Si,Sj) 都要满足:Si % Sj = 0 或 Sj % Si = 0。

    Michael阿明
  • LeetCode 1262. 可被三整除的最大和(DP)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/greatest-sum-divisible-by-t...

    Michael阿明

扫码关注云+社区

领取腾讯云代金券