Contains Duplicate
你会得到一个整数数组 nums。如果其中某个值至少出现两次，就返回 true；如果每个值都不同，则返回 false。
函数
- numsinteger-array
- 要检查的整数
- 返回值boolean
- 如果某个值至少出现两次，则为 true，否则为 false
约束条件
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109
示例
- 输入
- nums = [3, 1, 4, 1, 5]
- 输出
- true
- 解释
- 值
1出现在索引 1 处，并且再次出现在索引 3 处，所以答案是true。
- 输入
- nums = [2, 7, 1, 8]
- 输出
- false
- 解释
2、7、1和8是四个不同的值，所以没有重复项。
- 输入
- nums = [-4, 4, 0]
- 输出
- false
- 解释
-4和4的绝对值相同，但它们是不同的数字；0只出现一次，所以答案是false。
进阶
你能不能一遇到第一个重复值就停止，而不是总是读完整个数组？
提示
逐个打开提示，每个都会多透露一点。
将每个值与其他所有值进行比较是可行的，但对于
10^4个值来说，大约需要进行5 × 10^7次比较。你可以记住已经遍历过的值的哪些信息？重复表示当前值是你之前遇到过的值。哈希集合可以在平均常数时间内回答“我之前遇到过这个值吗？”
用一个空集合遍历数组一次。对于每个值，如果它已经在集合中，就返回
true；否则将它添加进去。如果循环结束，说明所有值都不相同。
题解
重复值是你之前遇到过的值，所以关键在于快速回答“我遇到过这个值吗？”。对于 n = 10^4，逐对比较大约需要 5 × 10^7 次比较。排序会让相等的值相邻，而哈希集合平均可以在 O(1) 时间内回答这个问题，因此只需遍历一次。
先排序，再比较相邻元素
思路
在排序后的数组中，相等的值会挨在一起：[3, 1, 4, 1, 5] 排序后变为 [1, 1, 3, 4, 5]，两个 1 紧挨着。因此，排序后只需将每个值与它前面的值比较，共需 n-1 次比较。
如果没有两个相邻值相等，那么任意位置的两个值也不会相等：在排序后的顺序中，两个 x 之间的任何值都既至少为 x，又至多为 x，所以它也会是另一个 x。
排序的时间复杂度占主导，为 O(n log n)。原地排序不需要额外的数组，但会重新排列调用方的输入；排序副本则需要 O(n) 空间。
算法
- 按升序对
nums排序。 - 让
i从 1 循环到最后一个索引。 - 如果
nums[i]等于nums[i-1]，返回true。 - 循环结束后，返回
false。
def containsDuplicate(nums):
nums.sort()
# After sorting, equal values sit next to each other.
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return False使用哈希集合遍历一次
思路
遍历数组一次，并将已经访问过的每个值都保存在哈希集合中。集合始终恰好保存当前位置之前的值，因此，命中表示当前值之前出现过；如果遍历到末尾都没有命中，就说明所有值都不相同。对于 [3, 1, 4, 1, 5]，第二个 1 到来时，集合中保存的是 {3, 1, 4}。
查找和插入的平均时间复杂度为 O(1)，因此遍历的时间复杂度为 O(n)。如果没有重复值，最终集合会保存全部 n 个值。
算法
- 创建一个空的哈希集合
seen。 - 对于
nums中的每个值，如果它在seen中，就返回true。 - 否则，将它添加到
seen中。 - 循环结束后，返回
false。
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
易错点和边界情况
- 在配对检查中，将内层循环从
j = i开始。这样每个值都会与自身匹配，答案总是true。 - 未先排序就比较相邻元素。在
[9, 1, 2, 3, 9]中，两个9并不相邻。 - 将相邻元素循环从索引 0 开始，并读取
nums[-1]。应从 1 开始，这样只有一个值的数组才能正确返回false。 - 把绝对值相同的值视为相等，例如对
abs(x)进行哈希。-4和4是不同的数字。
常见问题3
Contains Duplicate 的时间复杂度是多少？
哈希集合解法的平均时间复杂度为 O(n)，需要使用 O(n) 的额外空间。先排序需要 O(n log n) 的时间；如果可以重新排列输入，则不需要额外数组。比较每一对元素需要 O(n²) 的时间。
你能在不使用额外空间的情况下解决“包含重复元素”问题吗？
可以，如果允许你重新排列数组：就地排序，然后将每个值与相邻值进行比较，用 O(n) 的集合换取 O(n log n) 的时间复杂度。如果不重新排列，也不使用额外内存，剩下的唯一选择就是进行 O(n²) 的成对检查。
将集合的大小与数组的长度进行比较，是一种有效的解决方案吗？
是的。用所有 nums 中的元素构建一个集合，并检查它是否比数组小。它的时间复杂度为 O(n)，空间复杂度为 O(n)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def containsDuplicate(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [3, 1, 4, 1, 5]
预期输出
true