Skip to content

Latest commit

 

History

History
 
 

220.Contains-Duplicate-III

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

220.Contains-Duplicate-III

首先明确一下题意,i和j必须是不相同的两个下标。否则无论何时,你取i==j,总是能够满足题意的。

此题没有什么高明之处,对于nums[i],将i之前长度为k的滑动窗口放入一个multiset中。我们只需要考察这个有序集合里是否存在数值大小在[nums[i]-t, nums[i]+t]间的元素。我们用Set.lower_bound(nums[i]-t)寻找第一个大于等于nums[i]-t的位置。我们只需要判断该位置的元素是否存在(即是否非Set.end()),以及是否落在期望区间内即可。我们不需要再考察上界的位置。