咨询你github上leetcode 220题的第一种解法

来源：3-4 即使简单的问题，也有很多优化的思路

stoneboy100200

2019-02-28

请问老师第220题，这题第一种解法为什么用set，而不用unorded_set，是因为unorder_set中没有lower_bound这个函数吗？一定要有序吗？另外如果是一样的元素岂不是会覆盖set里已有的那个元素吗？这样有影响吧？

写回答

2回答

liuyubobobo

2019-02-28

已采纳

1）对，第一种方法使用set是因为有lower_bound，因为set本质是二分搜索树（红黑树），所以可以在logn的时间内查找到树中某一个数据的前驱或者后继。否则应该会超时。

2）整个算法的record中，存储了距离当前考察的元素（i）为k的所有元素。（33，34行在维护着一点），所以，如果在这个距离范围内有重复值，说明他们的差值为0，肯定满足任意给定的t。所以，在这个范围里，有重复值，我们直接就返回true了（一定满足27行的判断）：）自己针对有重复值的测试用例，实际运行这个程序，使用debug的方式一步一步跟踪，看一看程序是怎么处理的？：）

3）也可以自己尝试使用unordered_set，按照你的思路实现一下试试看？看是否可以，会有什么问题？（可能是可以完成的，届时分享一下你的想法：））

加油！：）