LeetCode 220. 存在重复元素 III

Categories:

题目描述
思路分析
1. 解法一：滑动窗口 + 有序集合（推荐）
相似题目

题目描述

✅ 220. 存在重复元素 III

思路分析

解法一：滑动窗口 + 有序集合（推荐）

核心思路：

维护大小为 k 的滑动窗口，用有序集合查询是否存在值在 [x - t, x + t]。

若存在，则满足条件。

每次移动窗口时加入当前值并移除过期值。

复杂度分析：

时间复杂度：O(n log k)，其中 n 表示数组长度。

空间复杂度：O(k)。

import java.util.TreeSet;

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k <= 0 || t < 0) {
            return false;
        }

        TreeSet<Long> set = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            long x = nums[i];
            Long ceil = set.ceiling(x - t);
            if (ceil != null && ceil <= x + t) {
                return true;
            }

            set.add(x);
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }

        return false;
    }
}

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
	if k <= 0 || t < 0 {
		return false
	}

	bucketSize := int64(t) + 1
	buckets := make(map[int64]int64)

	getBucket := func(x int64) int64 {
		if x >= 0 {
			return x / bucketSize
		}
		return (x+1)/bucketSize - 1
	}

	for i, v := range nums {
		x := int64(v)
		id := getBucket(x)

		if _, ok := buckets[id]; ok {
			return true
		}
		if val, ok := buckets[id-1]; ok && x-val <= int64(t) {
			return true
		}
		if val, ok := buckets[id+1]; ok && val-x <= int64(t) {
			return true
		}

		buckets[id] = x
		if i >= k {
			old := int64(nums[i-k])
			bid := getBucket(old)
			delete(buckets, bid)
		}
	}

	return false
}

相似题目

题目	难度	考察点
220. 存在重复元素 III	中等	滑动窗口、BST
219. 存在重复元素 II	简单	滑动窗口
217. 存在重复元素	简单	哈希
480. 滑动窗口中位数	困难	有序集合
1438. 绝对差不超过限制的最长连续子数组	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2020/66367910