LeetCode Contains Duplicate II

LeetCode Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j]and the difference between i and j is at most k.


本题是LeetCode Contains Duplicate的升级版,要求是判断是否有距离不超过k的两个相同的数。

首先想到暴力方法,一种是直接两层长度为n的循环,判断是否有距离不超过k的两个相等的数,另一种是外层循环为n,内层只要循环长度k,因为即使超过k有相等数的,也不符合题意。尝试之后显然超时。

然后我想到了另一种方法,把数组中所有相同数字的下标都放到一个桶里,后续再在这个桶里看是否有距离不超过k的两个下标对;如果桶里只有一个下标,说明这个下标对应的数没有重复出现,直接continue。完整代码如下:

class Solution {
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		if (nums.size() == 0)return false;
		unordered_map<int, int> hash_table;
		int distinct_cnt = 1; // 相异元素的个数
		vector<vector<int>> duplicate_indices = { {} }; // 跳过第0个桶
		for (int i = 0; i < nums.size(); i++) {
			if (hash_table[nums[i]] == 0) {
				hash_table[nums[i]] = distinct_cnt++;
				duplicate_indices.push_back({ i });
			}
			else {
				duplicate_indices[hash_table[nums[i]]].push_back(i); // 把相同元素的下标都放到一个桶里
			}
		}
		for (int i = 1; i < duplicate_indices.size(); i++) { // 查每个桶
			if (duplicate_indices[i].size() < 2)continue;
			for (int u = 0; u < duplicate_indices[i].size() - 1; u++) {
				for (int v = u + 1; v < duplicate_indices[i].size(); v++) {
					if (duplicate_indices[i][v] - duplicate_indices[i][u] <= k)return true;
				}
			}
		}
		return false;
	}
};

本代码提交AC,用时46MS。

后来看欣欣的解法LeetCode Contains Duplicate II,发现这个解法好厉害啊,用到了高级的unordered_set,之前只用过unordered_map,赶紧来学习一下。

她的思路是这样的,题目要求相同元素的距离不超过k,则我们维护一个长度为k的滑动窗口,把这个窗口里的所有数都hash到unordered_set里,后续每来一个元素,去这个hash_set里查之前是否出现过,因为我们的hash_set里只保留了前k个元素,所以如果hash_set查到了,他们的距离肯定是不超过k的。这种解法真是漂亮!完整代码如下:

class Solution {
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		if (nums.size() == 0 || k <= 0)return false;
		if (k >= nums.size())k = nums.size() - 1;
		unordered_set<int> hash_set;
		for (int i = 0; i < nums.size(); i++) {
			if (i > k)hash_set.erase(nums[i - k - 1]); // 滑动窗口,删掉窗口第一个元素
			if (hash_set.find(nums[i]) != hash_set.end())return true;
			hash_set.insert(nums[i]); // 把新元素插入窗口
		}
		return false;
	}
};

本代码提交AC,用时29MS,果然比我的速度快,厉害~

二刷。用一个hash表记录每个数最近出现的下标,如果新来一个数,之前在hash表中出现过,则看看下标之差是否小于等于k,是则返回true;否则更新hash。

思路非常简单,代码如下:

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

本代码提交AC,用时35MS。

One thought on “LeetCode Contains Duplicate II

  1. Pingback: LeetCode Contains Duplicate III | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *