[leetcode]217.存在重复元素

[MagicalBridge]

方法一：排序

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

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
 // 将数组做升序排列
 nums.sort((a, b) => a - b);
 // 数组的长度
 const n = nums.length;
 // 循环遍历数组 因为下面需要有 i+1的操作，所以这里n-1是取不到的。
 for (let i = 0; i < n - 1; i++) {
 if (nums[i] === nums[i + 1]) {
 return true;
 }
 }
 return false;
};

复杂度分析

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

方法二：哈希表

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

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
 const set = new Set();
 for (const x of nums) {
 if (set.has(x)) {
 return true;
 }
 set.add(x);
 }
 return false;
};

复杂度分析:

• 时间复杂度：O(N),其中N为数组的长度。
• 空间复杂度：O(N),其中N为数组的长度。