LeetCode每日一题217：存在重复元素

今天是一道简单的算法题, 然而我却被LeetCode新提交的测试用例卡住了!

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

示例 2:

示例 3:

暴力解法

不出意外的, 这种时间复杂度达到 的方法用 Python 实现超时

空间换时间思想

想看正确答案, 跳过这部分

如果这道题限定了数字的范围小于等于数组大小,那么这种方法可以获得接近 的时间复杂度.

判断的方法是构建一个与数组 ,若 ,则此位置为空, 改为1, 若非零则重复.

但是题目中没有限定, 这意味着负数、大于数组大小的数都可以使用,下面是错误示范 .

我想到了用类似散列线性探测法的方法, 用 是否为0判断有无重复, 为0则赋值为 但是小于数组的的数商为0,于是我在后面+1.但是这样还是不能覆盖所有样例, 因为还有负数的情况, 于是我有用了一个变量与结果相乘, 再进行判断.

然而还是无法覆盖......这次已经到达第17个样例, 什么问题呢? 就是当你的商为-1的时候, +1会变成0,这样又冲突了....

如果你有兴趣, 可以试试改这段代码, 让它通过测试, 估计速度不会特别差.

正解

哈希是最快的算法, 其次是用快速排序, 结合遍历.

Python在这里显示出极强的简洁性, 用集合自带的哈希算法, 只需一条语句就可以实现

下面这个解法是网友给出的, 答案非常简洁, 结构是双层嵌套, 但是运行结果居然才8ms, 很神奇. 不知道是不是测试例子不够极端.