题解 | #数组中的最长连续子序列#
数组中的最长连续子序列
http://www.nowcoder.com/practice/eac1c953170243338f941959146ac4bf
关键点
- 使用 Set 去重
- 向左向右查找连续的数字
- 优化:记录遍历过的点,下次直接跳过
export function MLS(arr: number[]): number {
const s = new Set(arr);
const tmp: { [key: number]: boolean } = {};
let max = 0;
for (let a of arr) {
if (!tmp[a]) {
let left = a - 1;
while (s.has(left)) {
tmp[left] = true;
left--;
}
let right = a + 1;
while (s.has(right)) {
tmp[right] = true;
right++;
}
max = Math.max(right - left - 1, max);
}
tmp[a] = true;
}
return max;
}