18-哈希表/LeetCode 第 220 题： 存在重复元素 III

LeetCode 第 220 题： 存在重复元素 III

我写的题解地址：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/hua-dong-chuang-kou-er-fen-sou-suo-shu-zhao-shang-/

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。

Java 代码：

import java.util.TreeSet;

public class Solution {

    /**
     * 要考虑到整型越界问题，所以要使用长整型
     *
     * @param nums
     * @param k    索引差：使用 TreeSet，使得 TreeSet 一共就存 k 个元素
     * @param t    数值的差
     * @return
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int len = nums.length;
        // 这里是或者
        if (len <= 1 || k <= 0) {
            return false;
        }
        TreeSet<Long> set = new TreeSet<>();
        int i = 0;
        while (i < len) {
            // 找不符合题目要求的情况
            Long floor = set.floor((long) nums[i]);
            Long ceiling = set.ceiling((long) nums[i]);
            boolean hasFloor = floor != null && nums[i] - floor <= t;
            boolean hasCeiling = ceiling != null && ceiling - nums[i] <= t;

            if (hasFloor || hasCeiling) {
                return true;
            }
            // 注意，这里应该取等号，因为前面在判断的时候，就相当于已经把元素加进去了
            // 而且从 nums[i - k] 表达式中也可以看出
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
            // 每一次都加入元素
            set.add((long) nums[i]);
            System.out.println("集合" + set);
            i++;
        }
        return false;
    }

    // 这个解法最好理解
    public boolean containsNearbyAlmostDuplicate2(int[] nums, int k, int t) {
        int len = nums.length;
        if (len == 0 || k <= 0 || t < 0) {
            return false;
        }
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int i = 0; i < len; i++) {
            Integer ceiling = treeSet.ceiling(nums[i]);
            if (ceiling != null && (long) ceiling - (long) nums[i] <= t) {
                return true;
            }
            Integer floor = treeSet.floor(nums[i]);
            if (floor != null && (long) nums[i] - (long) floor <= t) {
                return true;
            }
            treeSet.add(nums[i]);
            if (i >= k) {
                treeSet.remove(nums[i - k]);
            }
        }
        return false;
    }
}

参考资料

详细可以查看 官方题解 的 方法二 （二叉搜索树） 。
但是其中给出的Java代码，并说

C++ 中的 std::set，std::set::upper_bound 和 std::set::lower_bound 分别等价于 Java 中的 TreeSet，TreeSet::ceiling 和 TreeSet::floor。

这句是不准确的。

简单的说，

std::set::upper_bound 是 >
std::set::lower_bound 是 >=

修改和调整之后，通过了测试。

答题
bool containsNearbyAlmostDuplicate(vector& nums, int k, int t)
{
set _set;
for (int i = 0; i < nums.size(); ++i)
{
auto s = _set.lower_bound((double)nums[i] - (double)t);
if (s != _set.end() && *s <= (double)nums[i] + (double)t)
{
return true;
}

    _set.insert(nums[i]);
    if (_set.size() > k) 
    {
        _set.erase(nums[i - k]);
    }
}
return false;

}
致谢

作者：ikaruga
链接：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/220-by-ikaruga/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。