携手创作，共同成长！这是我参加「日新方案 8 月更文挑战」的第15天，点击检查活动概况

标题

给你一个整数数组 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
    }
}

复杂度剖析

• 时刻复杂度：$O(N\log N)$，其间 $N$ 为数组的长度。需要对数组进行排序。扫描的时刻复杂度 $O(n)$ 可忽略

• 空间复杂度：$O(1)$。 没有用到额定空间。假如深究 newNums.sort() 使用了栈空间，那就是 $O(logN)$，其间 $N$ 为数组的长度。注意咱们在这里应当考虑递归调用栈的深度。

方法二：字典

思路及解法

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

代码

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
    }
}

复杂度剖析

• 时刻复杂度：$O(N)$，其间 $N$ 为数组的长度。

• 空间复杂度：$O(N)$，其间 $N$ 为数组的长度。

方法三：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
    }
}

复杂度剖析

• 时刻复杂度：$O(N)$，其间 $N$ 为数组的长度。

• 空间复杂度：$O(N)$，其间 $N$ 为数组的长度。