LeetCode 题解工作台
存在重复元素
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。 示例 1： 输入： nums = [1,2,3,1] 输出： true 解释： 元素 1 在下标 0 和 3 出现。 示例 2： 输入： nums = [1,2,3,…
3
题型
10
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们先对数组 `nums` 进行排序。 然后遍历数组，如果存在相邻两个元素相同，说明数组中存在重复元素，直接返回 `true`。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
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 <= nums.length <= 105-109 <= nums[i] <= 109
解题思路
方法一：排序
我们先对数组 nums 进行排序。
然后遍历数组，如果存在相邻两个元素相同，说明数组中存在重复元素，直接返回 true。
否则，遍历结束，返回 false。
时间复杂度 。其中 是数组 nums 的长度。
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return any(a == b for a, b in pairwise(sorted(nums)))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect candidates to use a hash set for linear-time duplicate detection.
- question_mark
Watch for proper handling of edge cases with minimal and maximal array sizes.
- question_mark
Consider discussions around early exit optimization and space versus time trade-offs.
常见陷阱
外企场景- error
Using nested loops leads to O(n^2) time, which is unnecessary for this pattern.
- error
Forgetting to handle negative integers or zero in the array can cause incorrect results.
- error
Not implementing early exit may waste time on large arrays even when duplicates exist early.
进阶变体
外企场景- arrow_right_alt
Return the indices of the first duplicate instead of a boolean.
- arrow_right_alt
Count the total number of duplicates rather than just detecting one.
- arrow_right_alt
Detect duplicates within a sliding window of size k instead of the whole array.