Easy

题目描述

给你一个整数数组 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 <= 10^5
  • -10^9 <= nums[i] <= 10^9

解题思路

这道题要求检测数组中是否存在重复元素，有三种常见的解决方案：

方法一：哈希表（推荐）

使用哈希集合存储已遍历的元素。遍历数组时，如果当前元素已在集合中，说明存在重复，直接返回 true；否则将元素加入集合。这是最直观且高效的方法。

方法二：排序

先对数组排序，然后检查相邻元素是否相等。如果相邻元素相等，说明存在重复。这种方法空间复杂度更低，但时间复杂度稍高。

方法三：暴力法

使用双重循环检查每对元素是否相等。这种方法简单但效率低，仅适用于小规模数据。

推荐使用方法一（哈希表），因为它在时间和空间上都有很好的平衡，代码简洁易懂，是工程实践中的首选方案。

代码实现

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> seen;
        for (int num : nums) {
            if (seen.count(num)) {
                return true;
            }
            seen.insert(num);
        }
        return false;
    }
};

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False

public class Solution {
    public bool ContainsDuplicate(int[] nums) {
        HashSet<int> seen = new HashSet<int>();
        foreach (int num in nums) {
            if (seen.Contains(num)) {
                return true;
            }
            seen.Add(num);
        }
        return false;
    }
}

var containsDuplicate = function(nums) {
    const seen = new Set();
    for (let num of nums) {
        if (seen.has(num)) {
            return true;
        }
        seen.add(num);
    }
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表方法排序方法
时间复杂度O(n)O(n log n)
空间复杂度O(n)O(1)

其中 n 为数组长度。哈希表方法需要额外的 O(n) 空间存储集合，但时间复杂度更优；排序方法空间复杂度为 O(1)（原地排序），但时间复杂度较高。

相关题目