时间轴

2025-11-13

init

题目：

P219 存在重复元素 II

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

O(n2)O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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)O(n)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
    }
};