重复元素值

Leetcode 219. 存在重复元素 II

给你一个整数数组 nums 和一个整数k，判断数组中是否存在两个 不同的索引i和j，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 10^5
• -109 <= nums[i] <= 10^9
• 0 <= k <= 10^5

方法一：哈希表

从左到右遍历数组 nums，当遍历到下标 i 时，如果存在下标 j < i使得 nums[i]=nums[j]，则当 i−j ≤ k 时即找到了两个符合要求的下标 j 和 i。

如果在下标 i 之前存在多个元素都和 nums[i] 相等，为了判断是否存在满足 nums[i]=nums[j] 且 \(i - j \le k\)的下标 j，应该在这些元素中寻找下标最大的元素，将最大下标记为 j，判断 \(i - j \le k\) 是否成立。

如果 \(i - j \le k\)，则找到了两个符合要求的下标 j 和 i；如果 i - j > k，则在下标 i 之前不存在任何元素满足与 \(\textit{nums}[i]\)相等且下标差的绝对值不超过 k，理由如下。

假设存在下标 \(j'\)满足 \(j' < j 且，则 \)i - j' > i - j\(，由于 \)i - j > k\(，因此必有 \)i - j' > k$。

因此，当遍历到下标 i 时，如果在下标 i 之前存在与相等的元素，应该在这些元素中寻找最大的下标 j，判断 \(i - j \le k\)是否成立。

可以使用哈希表记录每个元素的最大下标。从左到右遍历数组 \(\textit{nums}\)，当遍历到下标 i 时，进行如下操作：

1. 如果哈希表中已经存在和 \(\textit{nums}[i]\)相等的元素且该元素在哈希表中记录的下标 j 满足 \(i - j \le k\)，返回 \(\text{true}\)；
2. 将 \(\textit{nums}[i]\) 和下标 \(i\) 存入哈希表，此时 \(i\) 是 \(\textit{nums}[i]\)的最大下标。

上述两步操作的顺序不能改变，因为当遍历到下标 i 时，只能在下标 i 之前的元素中寻找与当前元素相等的元素及该元素的最大下标。

当遍历结束时，如果没有遇到两个相等元素的下标差的绝对值不超过k，返回 \(\text{false}\)。

代码：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> dictionary;
        int length = nums.size();
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (dictionary.count(num) && i - dictionary[num] <= k) {
                return true;
            }
            dictionary[num] = i;
        }
        return false;
    }
};

• 时间复杂度：\(O(n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。需要遍历数组一次，对于每个元素，哈希表的操作时间都是 \(O(1)\)。
• 空间复杂度：\(O(n)\)，其中 \(n\) 是数组 \(\textit{nums}\)的长度。需要使用哈希表记录每个元素的最大下标，哈希表中的元素个数不会超过 \(n\)。

方法二：滑动窗口

考虑数组 \(\textit{nums}\)中的每个长度不超过 \(k + 1\) 的滑动窗口，同一个滑动窗口中的任意两个下标差的绝对值不超过 k。如果存在一个滑动窗口，其中有重复元素，则存在两个不同的下标 i 和 j 满足 \(\textit{nums}[i] = \textit{nums}[j]\)且 \(|i - j| \le k\)。如果所有滑动窗口中都没有重复元素，则不存在符合要求的下标。因此，只要遍历每个滑动窗口，判断滑动窗口中是否有重复元素即可。

如果一个滑动窗口的结束下标是 i，则该滑动窗口的开始下标是 \(\max(0, i - k)\)。可以使用哈希集合存储滑动窗口中的元素。从左到右遍历数组 \(\textit{nums}\)，当遍历到下标 i 时，具体操作如下：

1. 如果 \(i > k\)，则下标 \(i - k - 1\) 处的元素被移出滑动窗口，因此将 \(\textit{nums}[i - k - 1]\)从哈希集合中删除；
2. 判断 \(\textit{nums}[i]\)是否在哈希集合中，如果在哈希集合中则在同一个滑动窗口中有重复元素，返回 \(\text{true}\)，如果不在哈希集合中则将其加入哈希集合。

当遍历结束时，如果所有滑动窗口中都没有重复元素，返回 \(\text{false}\)。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> s;
        int length = nums.size();
        for (int i = 0; i < length; i++) {
            if (i > k) {
                s.erase(nums[i - k - 1]);
            }
            if (s.count(nums[i])) {
                return true;
            }
            s.emplace(nums[i]);
        }
        return false;
    }
};

• 时间复杂度：\(O(n)\)，其中 n 是数组 \(\textit{nums}\) 的长度。需要遍历数组一次，对于每个元素，哈希集合的操作时间都是 \(O(1)\)。
• 空间复杂度：\(O(k)\)，其中 k 是判断重复元素时允许的下标差的绝对值的最大值。需要使用哈希集合存储滑动窗口中的元素，任意时刻滑动窗口中的元素个数最多为 \(k + 1\)个。

重复元素范围

Leetcode 220. 存在重复元素 III

给你一个整数数组 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 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 104
• 0 <= t <= 2^31 - 1

方法一：滑动窗口 + 有序集合

思路及算法

对于序列中每一个元素 x 左侧的至多 k 个元素，如果这 k 个元素中存在一个元素落在区间 [x - t, x + t]中，我们就找到了一对符合条件的元素。注意到对于两个相邻的元素，它们各自的左侧的 k 个元素中有 k - 1个是重合的。于是我们可以使用滑动窗口的思路，维护一个大小为 k 的滑动窗口，每次遍历到元素 x 时，滑动窗口中包含元素 x 前面的最多 k 个元素，我们检查窗口中是否存在元素落在区间 [x - t, x + t]中即可。

如果使用队列维护滑动窗口内的元素，由于元素是无序的，我们只能对于每个元素都遍历一次队列来检查是否有元素符合条件。如果数组的长度为 n，则使用队列的时间复杂度为 \(O(nk)\)，会超出时间限制。

因此我们希望能够找到一个数据结构维护滑动窗口内的元素，该数据结构需要满足以下操作：

• 支持添加和删除指定元素的操作，否则我们无法维护滑动窗口；
• 内部元素有序，支持二分查找的操作，这样我们可以快速判断滑动窗口中是否存在元素满足条件，具体而言，对于元素 x，当我们希望判断滑动窗口中是否存在某个数 y 落在区间[x - t, x + t]中，只需要判断滑动窗口中所有大于等于 x - t的元素中的最小元素是否小于等于 x + t 即可。

我们可以使用有序集合来支持这些操作。

实现方面，我们在有序集合中查找大于等于 x - t的最小的元素 y，如果 y 存在，且 \(y \leq x + t\)，我们就找到了一对符合条件的元素。完成检查后，我们将 x 插入到有序集合中，如果有序集合中元素数量超过了 k，我们将有序集合中最早被插入的元素删除即可。

注意

如果当前有序集合中存在相同元素，那么此时程序将直接返回 \(\texttt{true}\)。因此本题中的有序集合无需处理相同元素的情况。

为防止整型 \(\texttt{int}\) 溢出，我们既可以使用长整型 \(\texttt{long}\)，也可以对查找区间[x - t, x + t]进行限制，使其落在 \(\texttt{int}\) 范围内。

代码：

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size();
        set<int> rec;
        for (int i = 0; i < n; i++) {
            auto iter = rec.lower_bound(max(nums[i], INT_MIN + t) - t);
            if (iter != rec.end() && *iter <= min(nums[i], INT_MAX - t) + t) {
                return true;
            }
            rec.insert(nums[i]);
            if (i >= k) {
                rec.erase(nums[i - k]);
            }
        }
        return false;
    }
};

• 时间复杂度：\(O(n \log(\min(n, k))\)，其中 n 是给定数组的长度。每个元素至多被插入有序集合和从有序集合中删除一次，每次操作时间复杂度均为 \(O(\log(\min(n, k))\)。
• 空间复杂度：\(O(\min(n, k))\)，其中 n 是给定数组的长度。有序集合中至多包含 \(\min(n, k + 1)\) 个元素。

方法二：桶排序

思路及算法

我们也可以使用利用桶排序的思想解决本题。我们按照元素的大小进行分桶，维护一个滑动窗口内的元素对应的元素。

对于元素 x，其影响的区间为[x - t, x + t]。于是我们可以设定桶的大小为 t + 1。如果两个元素同属一个桶，那么这两个元素必然符合条件。如果两个元素属于相邻桶，那么我们需要校验这两个元素是否差值不超过 t。如果两个元素既不属于同一个桶，也不属于相邻桶，那么这两个元素必然不符合条件。

具体地，我们遍历该序列，假设当前遍历到元素 x，那么我们首先检查 x 所属于的桶是否已经存在元素，如果存在，那么我们就找到了一对符合条件的元素，否则我们继续检查两个相邻的桶内是否存在符合条件的元素。

实现方面，我们将 \(\texttt{int}\)范围内的每一个整数 x 表示为 \(x = (t + 1) \times a + b(0 \leq b \leq t)\)的形式，这样 x 即归属于编号为 a的桶。因为一个桶内至多只会有一个元素，所以我们使用哈希表实现即可。

代码：

class Solution {
public:
    int getID(int x, long w) {
        return x < 0 ? (x + 1ll) / w - 1 : x / w;
    }

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        unordered_map<int, int> mp;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            long x = nums[i];
            int id = getID(x, t + 1ll);
            if (mp.count(id)) {
                return true;
            }
            if (mp.count(id - 1) && abs(x - mp[id - 1]) <= t) {
                return true;
            }
            if (mp.count(id + 1) && abs(x - mp[id + 1]) <= t) {
                return true;
            }
            mp[id] = x;
            if (i >= k) {
                mp.erase(getID(nums[i - k], t + 1ll));
            }
        }
        return false;
    }
};

• 时间复杂度：\(O(n)\)，其中 \(n\) 是给定数组的长度。每个元素至多被插入哈希表和从哈希表中删除一次，每次操作的时间复杂度均为 \(O(1)\)。
• 空间复杂度：\(O(\min(n, k))\)，其中 \(n\) 是给定数组的长度。哈希表中至多包含 \(\min(n, k + 1)\)个元素。

桶的解法相当凝练，不过有一点可以啰嗦两句。不知道有没有人疑惑，在比较id - 1和id + 1这两个相邻桶时，只比较了一个元素，这足够吗？哈希表的行为不是会用新元素覆盖旧元素，一个桶里有多个元素怎么办？

其实是覆盖根本不会发生...因为一旦要覆盖，就说明存在两个元素同属一个桶，直接返回true了。这就是题解说的“一个桶内至多只会有一个元素”——数组输入里当然可以有多个元素属于同一个桶，但是一旦出现一对，算法就结束了。

很多小伙伴对getID有点迷惑,就是为什么取负数,如w=10, 因为非负数是0~9，10~19...这种一组，而负数是-1~-10, -11~-20...这些是一组，如果-1~-10直接除以10，会被分到两组中，而不是-1这一组，所以先+1变成-0~-9,与正数一致，再除以10，最后减1，正好是-1这一组，其它组也是同理。