問題：
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.
大意：
給出一個(gè)整型數(shù)組和一個(gè)整型數(shù)k挚赊，判斷數(shù)組中是否任何兩個(gè)不一樣的位置i和j劣摇，如果 nums[i] = nums[j] ，i和j的距離不大于k生音。
思路：
這道題看起來(lái)簡(jiǎn)單，不過有很多陷阱跺株，比如如果k = 0苍日，那么無(wú)論數(shù)組如何都是錯(cuò)的。如果數(shù)組中不存在一樣的兩個(gè)數(shù)针姿，也是錯(cuò)的袱吆。如果數(shù)組中存在多個(gè)一樣的同一個(gè)數(shù)，只要有最短的兩個(gè)的距離小于等于k就可以了等等距淫，我把代碼縫縫補(bǔ)補(bǔ)后杆故，還是在一個(gè)很長(zhǎng)數(shù)組的測(cè)試用例下超時(shí)了。溉愁。处铛。不過我用的是最直接的方法，看了看如果合理地使用一些數(shù)據(jù)結(jié)構(gòu)拐揭，就會(huì)很方便撤蟆，比如使用set，set集合的特性是里面不會(huì)出現(xiàn)兩個(gè)不一樣的數(shù)字堂污，那么我們建立一個(gè)長(zhǎng)度為k的set家肯，用它來(lái)掃描整個(gè)數(shù)組，不斷地判斷新出現(xiàn)的數(shù)據(jù)能不能放進(jìn)去盟猖，如果不能放進(jìn)去讨衣，說(shuō)明存在距離小于等于k的數(shù)據(jù)是有相等的，否則就可以放進(jìn)去式镐，當(dāng)然set中的數(shù)據(jù)量如果超過k了就要同時(shí)把早先放進(jìn)去的數(shù)據(jù)拿出來(lái)了反镇，如果掃描過后都可以放進(jìn)去和取出來(lái)，說(shuō)明沒找到小于等于k的相等的數(shù)娘汞，那就錯(cuò)了歹茶。
這道題有個(gè)地方不一樣在于，一般的題目都是碰到什么就返回false你弦，都沒有false才返回true惊豺。而這道題卻是遇到什么則返回true，都沒有true禽作，才返回false尸昧。
他山之石：
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++){
if(i > k) set.remove(nums[i-k-1]);
if(!set.add(nums[i])) return true;
}
return false;
}
合集：https://github.com/Cloudox/LeetCode-Record
