面试经典150题 P219 存在重复元素 II

---

时间轴

时间轴

2025-11-13

init

哈希表

---

题目：

P219 存在重复元素 II

https://leetcode.cn/problems/contains-duplicate-ii/description/?envType=study-plan-v2&envId=top-interview-150

$O(n^2)$

#include <cstdlib>
#include <vector>
#include <unordered_map>

using std::unordered_map;
using std::vector;

class Solution {
    public:
	bool containsNearbyDuplicate(vector<int> &nums, int k)
	{
		int i, j, n = nums.size();
		unordered_map<int, vector<int> > num2index;

		for (i = 0; i < n; i++)
			num2index[nums[i]].push_back(i);

		for (auto &[_, index_vec] : num2index) {
			if (index_vec.size() > 1) {
				n = index_vec.size();

				for (i = 0; i < n; i++) {
					for (j = i + 1; j < n; j++) {
						if (std::abs(index_vec[i] - index_vec[j]) <= k) {
							return true;
						}
					}
				}
			}
		}
		return false;
	}
};

$O(n)$

一次遍历就行，遍历时保存上次的相同的值，因为上次 value 相同的值，其 index 距离当前遍历到的索引下标最近，即最有可能满足$abs(i - j) <= k$。

#include <unordered_map>
#include <vector>

using std::vector;
using std::unordered_map;

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> lastIndex;

        for (int i = 0; i < nums.size(); ++i) {
            if (lastIndex.count(nums[i]) && i - lastIndex[nums[i]] <= k)
                return true;

            lastIndex[nums[i]] = i;
        }
        return false;
    }
};