题解 | #数组中的最长连续子序列#

数组中的最长连续子序列

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;
}
全部评论

相关推荐

头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务