题目

给你一个整数数组 nums。如果任一值在数组中出现至少两次 ，返回 true；如果数组中每个元素互不相同，返回 false。

示例 1：

• 输入：nums = [1,2,3,1]
• 输出：true

示例 2：

• 输入：nums = [1,2,3,4]
• 输出：false

示例 3：

• 输入：nums = [1,1,1,3,3,4,3,2,4,2]
• 输出：true

方法一：排序

思路及解法

在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。因此，我们可以扫描已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。

代码

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        var newNums: [Int] = nums
        newNums.sort()
        for i in 0..<(newNums.count - 1) {
            if newNums[i] == newNums[i + 1] {
                return true
            }
        }
        return true
    }
}

复杂度分析

• 时间复杂度：，其中 为数组的长度。需要对数组进行排序。扫描的时间复杂度 可忽略

• 空间复杂度：。 没有用到额外空间。如果深究 newNums.sort() 使用了栈空间，那就是 ，其中 为数组的长度。注意我们在这里应当考虑递归调用栈的深度。

方法二：字典

思路及解法

对于数组中每个元素，我们将它存储到字典中。如果存储一个元素时发现该元素已经存在于字典中，则说明存在重复的元素。

代码

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        var numMap: [Int:Int] = [:]
        for num in nums {
            if nil != numMap[num] {
                return true
            }
            numMap[num] = num
        }
        return false
    }
}

复杂度分析

• 时间复杂度：，其中 为数组的长度。

• 空间复杂度：，其中 为数组的长度。

方法三：Set

思路及解法

遍历数组，数字放到 set 中。如果数字已经存在于 set 中，直接返回 true。如果成功遍历完数组，则表示没有重复元素，返回 false。

代码

class Solution {
    func containsDuplicate(_ nums: [Int]) -> Bool {
        var set = Set<Int>()
        for n in nums {
            if set.contains(n) {
                return true
            }
            set.insert(n)
        }
        return false
    }
}

复杂度分析

• 时间复杂度：，其中 为数组的长度。

• 空间复杂度：，其中 为数组的长度。