Leetcode 2026-08-21 题目分享

离散化 + 滑动窗口 + 树状数组。

LCR 057. 存在重复元素 III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个不同下标 i 和 j，使得：

abs(nums[i] - nums[j]) <= t
abs(i - j) <= k

如果存在则返回 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

提示：

0 <= nums.length <= 2 * 10^4
−2³¹ ≤ nums[i] ≤ 2³¹ − 1
0 <= k <= 10^4
0 ≤ t ≤ 2³¹ − 1

思路

同时满足下标差和数值差两个条件，可以从滑动窗口入手。遍历到下标 i 时，只需要在前面的 [i-k, i-1] 中查找是否存在元素值落在 [nums[i]-t, nums[i]+t] 内。
nums[i] 的取值范围很大，而数组长度只有 2 * 10^4，所以先将数组排序去重，把每个值离散化为从 1 开始的排名。
用树状数组维护当前窗口内每个离散值出现的次数。query(x) 可以求出排名不超过 x 的元素数量。
bs(v) 返回所有离散值中小于等于 v 的最大排名，因此区间 [v-t, v+t] 内的元素数量为：

query(bs(v+t)) - query(bs(v-t-1))
每次查询前先删除已经离开窗口的 nums[i-k-1]，查询完再将当前值加入树状数组。这样既能保证下标差不超过 k，也不会让当前元素与自己匹配。

代码

import "slices"

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
    mp, set, n := map[int]int{}, []int{}, 0

    // 排序去重，将每个数值离散化为从 1 开始的排名。
    for _, v := range slices.Sorted(slices.Values(nums)) {
        if _, ok := mp[v]; !ok {
            n++
            mp[v] = n
            set = append(set, v)
        }
    }

    // 返回 set 中小于等于 v 的最大排名；不存在时返回 0。
    bs := func(v int) int {
        l, r := 0, n-1
        for l <= r {
            mid := (l + r) >> 1
            if set[mid] > v {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        if r < 0 {
            return 0
        }
        return mp[set[r]]
    }

    tr := make([]int, n+1)
    update := func(idx, v int) {
        for i := idx; i <= n; i += i & -i {
            tr[i] += v
        }
    }
    query := func(idx int) int {
        sum := 0
        for i := idx; i > 0; i -= i & -i {
            sum += tr[i]
        }
        return sum
    }

    for i, v := range nums {
        // 使树状数组中只保留下标 [i-k, i-1] 内的元素。
        if i-k-1 >= 0 {
            update(mp[nums[i-k-1]], -1)
        }

        cur := query(bs(v+t)) - query(bs(v-t-1))
        if cur > 0 {
            return true
        }
        update(mp[v], 1)
    }
    return false
}

复杂度分析

时间：O(nlog n)。离散化需要排序，每个元素又会进行常数次二分和树状数组操作。
空间：O(n)。离散化数组、映射和树状数组均与输入规模同阶。