波波老师，set.size()==k+1不代表两个索引之差最多就是K吧？如果两个索引之差为K+1的数组范围内，只有不到K个不同的元素，那不就违反题意了吗

来源：4-7 查找表和滑动窗口 Contain Duplicate II

芒果和芒果柠檬

2018-07-06

写回答

1回答

liuyubobobo

2018-07-07

已采纳

set是在遍历数组的过程中逐渐添加元素的。当set.size() == k + 1，表示我们已经连续看了 k + 1个元素（索引差为k），都不存在重复的元素。这里关键词是“连续”。所以，如果set.size() == k + 1了，整个数组至少有k + 1个元素：）

我不确定我完全理解了你的问题。如果你觉得自己的思考是正确的话，可以给出一个让这个算法出错的测试用例：）或者对于你认为会出问题的测试用例，实际用这个算法跑一下，跟进程序里看看会发生什么，和自己想的是否一样。针对特殊测试用例跟踪算法的每一步调用，理解算法运行的内部机理，是学习算法的关键方法哦：）

加油！

郭爱斌

我是用hashmap写的，不过还好。回来看了你的算法，刚开始也有些疑问，看了你的解释也豁然开朗了，算法的意思是：前面如果有相同的元素就返回true，若没有，则加入set中，是不重复的元素。

2019-01-10

共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7408 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 2

回答 1