目录
1，题目
2，代码
2.1自己实现
2.2哈希表
3，学习与收获
枚举思想：
遍历的核心逻辑
碎碎念
本题 先是想到利用数组排序，从而简化遍历处理逻辑，再在提交错误提醒的情况下，考虑到数组中存在重复数字的情况，从而进一步完善自己的代码逻辑，即先对数组进行去重，再排序，最后实现计数最长连续数列的逻辑；
题解中学习到： 1是连续数列中最优的匹配情况是从数列的开头数字开始，也就是不存在其前驱项；2是合理利用数据结构，从而实现更好时间复杂度下对目标数的查找：利用set实现对x-1 和 num +1的线性查找；
1，题目
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
2，代码
2.1自己实现
步骤：
- 第一步：对数组进行去重，得到数组arr；
- 第二步：对arr数组进行排序，得到数组arrSort；
- 第三步：循环遍历数组arrSort，找到最长的连续数列；
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
const len = nums.length;
if (len === 0) return 0;
// 先去重
const arr = Array.from(new Set(nums))
// 进行排序
const arrsSort = arr.sort((a,b)=>a-b);
let max = 1;
let temp = 1;
for(let i = 1; i < arrsSort.length; i++){
if(arrsSort[i] - 1 === arrsSort[i-1]){
temp++;
}else{
max = Math.max(temp,max);
temp = 1;
}
}
// 遍历完全后 对max值进行一次更新
max = Math.max(temp,max);
return max;
};2.2哈希表
利用哈希表实现数据查找的O(1)时间复杂度；
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
// 去重且利用set数据结构 实现O(1)查找数据
let hashtable = new Set(nums);
// 当数组为空或只包含重复元素时，应返回0，以正确处理空数组的情况。
let max = 0;
for(let item of hashtable){
if(!hashtable.has(item - 1)){
let currentNum = item;
let currentStreak = 1;
while(hashtable.has(currentNum + 1)){
currentNum += 1;
currentStreak += 1;
}
max = Math.max(max, currentStreak);
}
}
return max;
};3，学习与收获
枚举思想：
考虑枚举数组中的每个数 x，考虑以其为起点，不断尝试匹配 x+1,x+2,⋯ 是否存在，假设最长匹配到了 x+y，那么以 x 为起点的最长连续序其长度为 y+1。仅仅是这样我们的算法时间复杂度最坏情况下还是会达到 O(n^2)（即外层需要枚举O(n) 个数，内层需要暴力匹配 O(n)次）。
如果已知有一个 x,x+1,x+2,⋯ ,x+y 的连续序列，而我们却重新从 x+1，x+2或者是 x+y 处开始尝试匹配，那么得到的结果肯定不会优于枚举 x 为起点的答案，因此我们在外层循环的时候碰到这种情况跳过即可。
那么怎么判断是否跳过呢？由于我们要枚举的数 x 一定是在数组中不存在前驱x−1 的，不然按照上面的分析我们会从x−1 开始尝试匹配，因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。
遍历的核心逻辑
for(let item of hashtable){
if(!hashtable.has(item - 1)){
let currentNum = item;
let currentStreak = 1;
while(hashtable.has(currentNum + 1)){
currentNum += 1;
currentStreak += 1;
}
max = Math.max(max, currentStreak);
}
}今儿二刷
自己实现
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
let left = 0,right = 0;
while(right < nums.length){
if(nums[right]!= val){
nums[left] = nums[right];
left++;
}
right++;
}
return left;
}优化后-再次学习
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
// [1,2,3,4,5]，当 val 为 1 时
let left = 0, right = nums.length - 1;
while(left <= right){
if(nums[left] === val){
while(left < right && nums[right] === val){
right--;
}
nums[left] = nums[right];
right--;
}
left++;
}
return right + 1; // 因为right是最后一个不等于val的元素的索引，所以长度是right+1
}勉励自己：贵在坚持！
