【算法-初级-数组】存在重复元素（JavaScript实现）
【算法-初级-数组】存在重复元素（JavaScript实现）
博客说明
文章所涉及的部分资料来自互联网整理，当然还有自己个人的总结和看法，分享的目的在于共建社区和巩固自己。引用的资料如有侵权，请联系本人删除！幸好我在，感谢你来！
算法说明
语言只是实现算法的一种手段，思路才是最为重要的。
如果有多种解法的话，只选一种语言作为解答对比。
如果单独将某一种算法的话，会以多种语言实现，对比语言的特性。
?因为多对多的话，篇幅会拉的比较大，影响观看体验！
题目
题目地址
题目说明
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1
输入: [1,2,3,1]
输出: tru
示例 2
输入: [1,2,3,4]
输出: false
示例 3
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
思路
暴力解法
怎么能缺少暴力解法呢，这毕竟是大脑最直白的想法，当然保留！?
直接遍历，拿一个辅助数组，一个一个往里面塞，直到遇到相等的，那么就是它！
这里就不贴代码了（暴力的解法毕竟不美观哈！），看一下结果！
但注意哈！不可耻！毕竟通过了✅。
排序
思路
在暴力解法的时候遇到了一个问题，就是时间和空间复杂度都比较高。
因为在辅助数组里面也需要遍历，因为原数组的不是按照顺序来的，所以需要我们来一场排序，会解决掉一些问题。
因为重复的元素都会在相邻的位置，只需要当前的元素左右扭头看一下即可。
JavaScript
之前是用的js写的暴力，所以对比js的排序改进版。
看下面的图，发现然而并没卵用，该高还是得高，时间有那么一点改进。
?因为排序也是需要开销的。
再来！
代码
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
if (nums.length < 1) return false
// 排序
nums.sort((a, b) => a - b)
const n = nums.length;
for (var i = 0; i < n - 1; i++) {
if (nums[i] === nums[i + 1]){
return true
}
}
return false
};
复杂度分析
时间复杂度
O(NlogN)，其中 N 为数组的长度。
需要对数组进行排序。
空间复杂度
O(logN)，其中 N 为数组的长度。
哈希表
思路
看我们暴力解法的时候，有两个比较麻烦的点，一个是不确定重复的元素的出现的位置（所以上一步来了排序），一个是需要辅助的数组来记录。
这次就利用哈希表来存储已遍历的元素，再次插入相同的元素的时候哈希表就能给出反应，只需要遍历就行！
JavaScript
代码
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
if (nums.length < 1) return false
// 哈希表
const set = new Set();
const n = nums.length;
for (var i = 0; i < n; i++) {
if (set.has(nums[i])) {
return true
}else {
set.add(nums[i])
}
}
return false
};
复杂度分析
时间复杂度
O(N)，其中 N 为数组的长度。
空间复杂度
O(N)，其中 N 为数组的长度。
感谢
万能的网络
公众号【归子莫】，小程序【小归博客】
如果你感觉对你有帮助的话，不妨给我点赞?吧，持续关注也行哈！