217. 存在重复元素
题目描述
输入整数数组 nums。只要有某个值出现了两次或更多，就返回 true。
如果所有元素都不相同，返回 false。
示例 1
输入：nums = [1,2,3,1] 输出：true
解释：1 在下标 0 和 3 各出现一次。
示例 2
输入：nums = [1,2,3,4] 输出：false
解释：四个元素各不相同。
示例 3
输入：nums = [1,1,1,3,3,4,3,2,4,2] 输出：true
解释：1、2、3、4 都出现了不止一次。
数据范围
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
解题思路：哈希集合
从左到右扫描，用哈希集合 seen 记住已经见过的数。读到 x 时先问「x 在 seen 里吗？」——在，说明前面出现过，立即返回 true；不在，就把 x 加入 seen 继续。扫完都没碰到重复，返回 false。
为什么正确
处理到下标 i 之前，seen 恰好是 nums[0..i-1] 中出现过的所有值，并且这些值两两不同。
复杂度分析
时间 O(n)（每个数一次 O(1) 平均的查询和插入），空间 O(n)。
易错点
必须先查再加：如果先 seen.add(x) 再判断 x in seen，每个数都会「撞上自己」而误判为 true。也可以排序后比较相邻元素（O(n log n)），但双重循环两两比较是 O(n²)，会超时。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return Falseclass Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int x : nums) {
if (seen.contains(x)) {
return true;
}
seen.add(x);
}
return false;
}
}class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> seen;
for (int x : nums) {
if (seen.count(x)) {
return true;
}
seen.insert(x);
}
return false;
}
};func containsDuplicate(nums []int) bool {
seen := map[int]bool{}
for _, x := range nums {
if seen[x] {
return true
}
seen[x] = true
}
return false
}var containsDuplicate = function(nums) {
const seen = new Set();
for (const x of nums) {
if (seen.has(x)) {
return true;
}
seen.add(x);
}
return false;
};function containsDuplicate(nums: number[]): boolean {
const seen = new Set<number>();
for (const x of nums) {
if (seen.has(x)) {
return true;
}
seen.add(x);
}
return false;
}其他解法
排序把重复元素变成相邻元素，用时间换空间；哈希集合用 O(n) 空间做到平均 O(n) 时间，并且能在遇到第一个重复元素时提前结束。
解法 2：排序 时间 O(n log n)，空间 O(log n)
先对数组排序，相同的元素会排在一起。再扫描一遍，只要有相邻两个元素相等就返回 true。
不需要哈希表，额外空间只有排序的递归栈。时间多一个 log 因子，而且会打乱原数组的顺序。
from typing import List
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return Falseclass Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) return true;
}
return false;
}
}class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 1; i < (int)nums.size(); i++) {
if (nums[i] == nums[i - 1]) return true;
}
return false;
}
};func containsDuplicate(nums []int) bool {
sort.Ints(nums)
for i := 1; i < len(nums); i++ {
if nums[i] == nums[i-1] {
return true
}
}
return false
}var containsDuplicate = function(nums) {
nums.sort((a, b) => a - b);
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1]) return true;
}
return false;
};function containsDuplicate(nums: number[]): boolean {
nums.sort((a, b) => a - b);
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1]) return true;
}
return false;
};