LeetCode 219.Contains Duplicate II

LeetCode 219.Contains Duplicate II

Description:

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 absolute difference between i and j is at most k.

Example 1:

Input: [1,2,3,1,2,3,4], k = 3
Output: True

Example 2:

Input: [1,2,3,1,2,3,4], k = 2
Output: False

---

分析：

首先，最简单的当然是两层循环，但肯定是超时的。
换一种思路，解决这种题目，经常会用到STL中的集合set；
在这道题中，我们可以把数组一个个放到集合s中去，利用集合元素不会重复的特性，可判断出已经出现的数字，也即是出现重复的数，此时再去循环判断两个重复数的位置与k的关系，小于等于k即为真。
代码中我们用了一个currentSize来记录当前集合s的大小，若外循环尝试插入一个数时s的大小不变，体现在代码中就是s.size() == currentSize，说明此时出现重复的数，内循环再判断之前出现该数的位置，两者相减后比较与k的关系，得出结果。

---

代码如下：

运行超时版本：

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

AC版本：

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
class Solution {
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		set<int> s;
		int currentSize = 0;// 记录当前集合s的大小
		for (int i = 0; i < nums.size(); i++) {
			s.insert(nums[i]);
			// 若相等，表示insert了一个已经出现过的数，即找到重复的数
			// 内循环遍历得到之前出现的数，两者相减后再与k比较，得出结果
			if (s.size() == currentSize) {
				for (int j = i - 1; j >= 0 && i - j <= k; j--) {
					if (nums[i] == nums[j]) return true;
				}
			}
			currentSize = s.size();
		}
		return false;
	}
};
int main() {
	Solution s;
	vector<int> nums;
	int n;
	cin >> n;
	int t;
	for (int i = 0; i < n; i++) {
		cin >> t;
		nums.push_back(t);
	}
	int k;
	cin >> k;
	cout << s.containsNearbyDuplicate(nums, k) << endl;
	return 0;
}