哈希表计算最长连续序列是否需要判断条件更新序列长度

Question

使用哈希表Map解决最长连续序列中的疑惑

var longestConsecutive = (nums) => {
  let map = new Map()
  let max = 0
  for (const num of nums) { // 遍历nums数组
    if (!map.has(num)) { // 重复的数字不考察，跳过
      let preLen = map.get(num - 1) || 0  // 获取左邻居所在序列的长度 
      let nextLen = map.get(num + 1) || 0 // 获取右邻居所在序列的长度 
      let curLen = preLen + 1 + nextLen   // 新序列的长度
      map.set(num, curLen) // 将自己存入 map
      max = Math.max(max, curLen) // 和 max 比较，试图刷新max
      map.set(num - preLen, curLen)  // 更新新序列的左端数字的value
      map.set(num + nextLen, curLen) // 更新新序列的右端数字的value
    }
  }
  return max
}

示例一：nums =
[100,4,200,1,3,2]

哈希表的方法我不太理解，没有排序的话，怎么知道成序列的。
比如遍历过程中，拿示例一举例，100，直接放入哈希表，key100，value1；
之后4放入哈希表，更新左侧序列长度吗？这里是不是需要添加一个判断是否更新序列左侧的数字。

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

【您想要解决的问题】：您提问的目的是理解在不排序的情况下，如何使用哈希表（Map）来解决最长连续序列的问题，并希望解决在遍历数组时如何确定和更新序列长度的问题。

【问题出现原因】：问题出现的原因可能在于对哈希表的工作原理和在本算法中的具体应用不够清晰。在没有排序的情况下，通过哈希表可以快速判断一个数字是否已经存在于序列中，以及它的前一个和后一个数字是否存在，从而确定是否可以形成连续序列。

【问题解决方案】：在给定的代码中，哈希表的键（key）是数字本身，而值（value）是该数字所在连续序列的长度。当遍历数组时，对于每个数字，算法会检查它的前一个和后一个数字是否存在于哈希表中。如果存在，就可以计算当前数字所在序列的长度，并更新哈希表中相应数字的值以及序列两端的值。

【提供代码】：代码本身已经能够解决最长连续序列的问题，但是为了清晰起见，我会对代码进行一些注释，以便更好地理解其工作原理。

var longestConsecutive = (nums) => {
  let map = new Map(); // 创建哈希表
  let max = 0; // 初始化最长序列长度为0

  for (const num of nums) { // 遍历nums数组
    if (!map.has(num)) { // 如果当前数字不在哈希表中，则进行处理
      let preLen = map.get(num - 1) || 0; // 获取前一个数字所在序列的长度，如果没有则为0
      let nextLen = map.get(num + 1) || 0; // 获取后一个数字所在序列的长度，如果没有则为0
      let curLen = preLen + 1 + nextLen; // 计算当前数字所在序列的长度

      // 将当前数字及其序列长度存入哈希表
      map.set(num, curLen);
      // 更新序列两端的数字的值，表示它们也是当前序列的一部分
      if (preLen === 0) map.set(num - preLen, curLen); // 如果前一个数字不在序列中，则更新
      if (nextLen === 0) map.set(num + nextLen, curLen); // 如果后一个数字不在序列中，则更新

      max = Math.max(max, curLen); // 更新最长序列长度
    }
  }
  return max; // 返回最长序列的长度
};

【代码运行方式】：这段代码是JavaScript代码，可以在任何支持JavaScript的环境下运行，例如浏览器的控制台或者Node.js环境。

【代码预期运行结果】：

Input: nums = [100,4,200,1,3,2]
Output: 4

解释：最长的连续序列是 [1, 2, 3, 4]，长度为4。

【推荐相关链接】：

1. MDN Web Docs - Map - 哈希表（Map）的官方文档。
2. W3Schools - JavaScript Map Object - JavaScript Map对象的教程。
3. LeetCode - Longest Consecutive Sequence - 最长连续序列问题的LeetCode页面，可以查看更多解决方案和讨论。