[数据结构与算法]算法：存在重复元素

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

提示：

• 1 <= nums.length <= 105

• -109 <= nums[i] <= 109

力扣链接

我的思路

循环数组，记录元素出现次数，放到对象中，{元素： 元素次数}，一旦元素次数>1就返回 true

const containsDuplicate = function(nums) {
	let obj = {}
	for (i of obj) {
		if (obj[i]) {
			obj[i] += 1
			return true;
		} else {
			obj[i] = 1
		}
		return false
}

但是，我这个方法的时间复杂度和空间复杂度真的无语了……下面我们看一下官方方法吧~

方法一：排序

在对数组排序之后，如果有重复元素，那么肯定会有相邻的两个元素是相等的

var containsDuplicate = function(nums) {
	let arr = nums.sort((a,b) => a-b)
	for (let i = 0; i < nums.length; i++) {
		if (nums[i] === nums[i + 1]) {
			return true;
		}
	} 
	return false;
}

复杂度分析

• 时间复杂度：O(N\log N)O(NlogN)，其中 NN 为数组的长度。需要对数组进行排序。
• 空间复杂度：O(\log N)O(logN)，其中 NN 为数组的长度。注意我们在这里应当考虑递归调用栈的深度

方法二：哈希表

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

set 对象

Set 对象存储的值总是唯一的

这里我们使用 set 对象的 has 方法来判断

var containsDuplicate = function(nums) {
	const set = new Set()
	for (const x of nums) {
		if (set.has(x)) {
			return true;
		}
		set.add(x)
	}
	return false;
}