220-存在重复元素 III(Contains Duplicate III)
发表于：2021-12-03 | 分类： 中等
字数统计: 173 | 阅读时长: 1分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/contains-duplicate-iii

英文原文

Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.

 

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 104
  • 0 <= t <= 231 - 1

中文题目

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

 

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

 

提示：

  • 0 <= nums.length <= 2 * 104
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 104
  • 0 <= t <= 231 - 1

通过代码

高赞题解

滑动窗口 & 二分

根据题意，对于任意一个位置 i（假设其值为 u），我们其实是希望在下标范围为 $[max(0, i - k), i)$ 内找到值范围在 $[u - t, u + t]$ 的数。

一个朴素的想法是每次遍历到任意位置 i 的时候，往后检查 k 个元素，但这样做的复杂度是 $O(nk)$ 的，会超时。

显然我们需要优化「检查后面 k 个元素」这一过程。

我们希望使用一个「有序集合」去维护长度为 k 的滑动窗口内的数，该数据结构最好支持高效「查询」与「插入/删除」操作：

  • 查询：能够在「有序集合」中应用「二分查找」，快速找到「小于等于 $u$ 的最大值」和「大于等于 u 的最小值」（即「有序集合」中的最接近 u 的数）。
  • 插入/删除：在往「有序集合」添加或删除元素时，能够在低于线性的复杂度内完成（维持有序特性）。

或许你会想到近似 $O(1)$ 操作的 HashMap，但注意这里我们需要找的是符合 $abs(nums[i], nums[j]) \leqslant t$ 的两个值，nums[i] 与 nums[j] 并不一定相等，而 HashMap 无法很好的支持「范围查询」操作。

我们还会想到「树」结构。

例如 AVL，能够让我们在最坏为 $O(\log{k})$ 的复杂度内取得到最接近 u 的值是多少，但本题除了「查询」以外，还涉及频繁的「插入/删除」操作（随着我们遍历 nums 的元素，滑动窗口不断右移，我们需要不断的往「有序集合」中删除和添加元素）。

简单采用 AVL 树，会导致每次的插入删除操作都触发 AVL 的平衡调整，一次平衡调整会伴随着若干次的旋转。

而红黑树则很好解决了上述问题：将平衡调整引发的旋转的次数从「若干次」限制到「最多三次」。

因此，当「查询」动作和「插入/删除」动作频率相当时，更好的选择是使用「红黑树」。

也就是对应到 Java 中的 TreeSet 数据结构（基于红黑树，查找和插入都具有折半的效率）。

IMG_1693.PNG

其他细节：由于 nums 中的数较大，会存在 int 溢出问题，我们需要使用 long 来存储。

代码（感谢 @Benhao 和 @wqs 提供的其他语言版本 ）：

[]
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> ts = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            Long u = nums[i] * 1L;
            // 从 ts 中找到小于等于 u 的最大值（小于等于 u 的最接近 u 的数）
            Long l = ts.floor(u); 
            // 从 ts 中找到大于等于 u 的最小值（大于等于 u 的最接近 u 的数）
            Long r = ts.ceiling(u); 
            if(l != null && u - l <= t) return true;
            if(r != null && r - u <= t) return true;
            // 将当前数加到 ts 中，并移除下标范围不在 [max(0, i - k), i) 的数（维持滑动窗口大小为 k）
            ts.add(u);
            if (i >= k) ts.remove(nums[i - k] * 1L);
        }
        return false;
    }
}
[]
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> st;
        for (int i = 0; i < nums.size(); i++) {
            auto lb = st.lower_bound((long)nums[i] - t);
            if (lb != st.end() && *lb <= (long)nums[i] + t) return 1;
            st.insert(nums[i]);
            if (i >= k) st.erase(nums[i - k]);
        }
        return 0;
    }
};
[]
from sortedcontainers import SortedList

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        # O(N logk)
        window = SortedList()
        for i in range(len(nums)):
            # len(window) == k
            if i > k:
                window.remove(nums[i - 1 - k])
            window.add(nums[i])
            idx = bisect.bisect_left(window, nums[i])
            if idx > 0 and abs(window[idx] - window[idx-1]) <= t:
                return True
            if idx < len(window) - 1 and abs(window[idx+1] - window[idx]) <= t:
                return True
        return False
  • 时间复杂度：TreeSet 基于红黑树，查找和插入都是 $O(\log{k})$ 复杂度。整体复杂度为 $O(n\log{k})$
  • 空间复杂度：$O(k)$

桶排序

上述解法无法做到线性的原因是：我们需要在大小为 k 的滑动窗口所在的「有序集合」中找到与 u 接近的数。

如果我们能够将 k 个数字分到 $k$ 个桶的话，那么我们就能 $O(1)$ 的复杂度确定是否有 $[u - t, u + t]$ 的数字（检查目标桶是否有元素）。

具体的做法为：令桶的大小为 $size = t + 1$，根据 u 计算所在桶编号：

  • 如果已经存在该桶，说明前面已有 $[u - t, u + t]$ 范围的数字，返回 true
  • 如果不存在该桶，则检查相邻两个桶的元素是有 $[u - t, u + t]$ 范围的数字，如有 返回 true
  • 建立目标桶，并删除下标范围不在 $[max(0, i - k), i)$ 内的桶

代码（感谢 @Benhao 和 @answerer 提供的其他语言版本 ）：

[]
class Solution {
    long size;
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        Map<Long, Long> map = new HashMap<>();
        size = t + 1L;
        for (int i = 0; i < n; i++) {
            long u = nums[i] * 1L;
            long idx = getIdx(u);
            // 目标桶已存在（桶不为空），说明前面已有 [u - t, u + t] 范围的数字
            if (map.containsKey(idx)) return true;
            // 检查相邻的桶
            long l = idx - 1, r = idx + 1;
            if (map.containsKey(l) && u - map.get(l) <= t) return true;
            if (map.containsKey(r) && map.get(r) - u <= t) return true;
            // 建立目标桶
            map.put(idx, u);
            // 移除下标范围不在 [max(0, i - k), i) 内的桶
            if (i >= k) map.remove(getIdx(nums[i - k] * 1L));
        }
        return false;
    }
    long getIdx(long u) {
        return u >= 0 ? u / size : ((u + 1) / size) - 1;
    }
}
[]
#define LL long long
class Solution {
public:
    LL size;
    bool containsNearbyAlmostDuplicate(vector <int> & nums, int k, int t) {
        int n = nums.size();
        unordered_map<LL, LL> m;
        size = t + 1L;
        for (int i = 0; i < n; i++) {
            LL u = nums[i] * 1L;
            LL idx = getIdx(u);
            // 目标桶已存在（桶不为空），说明前面已有 [u - t, u + t] 范围的数字
            if (m.find(idx) != m.end()) return true;
            // 检查相邻的桶
            LL l = idx - 1, r = idx + 1;
            if (m.find(l) != m.end() && abs(u - m[l]) <= t) return true;
            if (m.find(r) != m.end() && abs(u - m[r]) <= t) return true;
            // 建立目标桶
            m.insert({idx, u});
            // 移除下标范围不在 [max(0, i - k), i) 内的桶
            if (i >= k) m.erase(getIdx(nums[i - k]));
        }
        return false;
    }
    LL getIdx(LL u) {
        return u >= 0 ? u / size : ((u + 1) / size) - 1;
    }
};
[]
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        def getIdx(u):
            return ((u + 1) // size) - 1 if u < 0 else u // size
        
        map = {}
        size = t + 1
        for i,u in enumerate(nums):
            idx = getIdx(u)
            # 目标桶已存在（桶不为空），说明前面已有 [u - t, u + t] 范围的数字
            if idx in map:
                return True
            # 检查相邻的桶
            l, r = idx - 1, idx + 1
            if l in map and abs(u - map[l]) <= t:
                return True
            if r in map and abs(u - map[r]) <= t:
                return True
            # 建立目标桶
            map[idx] = u
            # 维护个数为k
            if i >= k:
                map.pop(getIdx(nums[i-k]))

        return False
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(k)$

【重点】如何理解 getIdx() 的逻辑

  1. 为什么 size 需要对 t 进行 +1 操作？

目的是为了确保差值小于等于 t 的数能够落到一个桶中。

举个 🌰，假设 [0,1,2,3]，t = 3，显然四个数都应该落在同一个桶。

如果不对 t 进行 +1 操作的话，那么 [0,1,2] 和 [3] 会被落到不同的桶中，那么为了解决这种错误，我们需要对 t 进行 +1 作为 size 。

这样我们的数轴就能被分割成：

0 1 2 3 | 4 5 6 7 | 8 9 10 11 | 12 13 14 15 | …

总结一下，令 size = t + 1 的本质是因为差值为 t 两个数在数轴上相隔距离为 t + 1，它们需要被落到同一个桶中。

当明确了 size 的大小之后，对于正数部分我们则有 idx = nums[i] / size。

  1. 如何理解负数部分的逻辑？

由于我们处理正数的时候，处理了数值 0，因此我们负数部分是从 -1 开始的。

还是我们上述 🌰，此时我们有 t = 3 和 size = t + 1 = 4。

考虑 [-4,-3,-2,-1] 的情况，它们应该落在一个桶中。

如果直接复用 idx = nums[i] / size 的话，[-4] 和 [-3,-2,-1] 会被分到不同的桶中。

根本原因是我们处理整数的时候，已经分掉了数值 0。

这时候我们需要先对 nums[i] 进行 +1 操作（即将负数部分在数轴上进行整体右移），即得到 (nums[i] + 1) / size。

这样一来负数部分与正数部分一样，可以被正常分割了。

但由于 0 号桶已经被使用了，我们还需要在此基础上进行 -1，相当于将负数部分的桶下标（idx）往左移，即得到 ((nums[i] + 1) / size) - 1。

统计信息

通过次数 提交次数 AC比率
67543 235388 28.7%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言

相似题目

题目 难度
存在重复元素 简单
存在重复元素 II 简单
排序 数组 滑动窗口 有序集合 桶排序
上一篇:
219-存在重复元素 II(Contains Duplicate II)
下一篇:
221-最大正方形(Maximal Square)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo