时间轴

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)$

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
#include <cstdlib>
#include <vector>
#include <unordered_map>

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

class Solution {
    public:
	bool containsNearbyDuplicate(vector<int> &nums, int k)
	{
		unordered_map<int, vector<int> > num2index;
		int i, j, n = nums.size();
		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)$

一次遍历就行，遍历时保存上次的相同的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <unordered_map>
#include <vector>
#include <cstdlib>
using namespace std;

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;
    }
};