最长连续序列

怎样从“在未排序数组 [100,4,200,1,3,2] 中找最长连续序列长度,要求 O(n)。”推导出 哈希集合 · 起点扩展，并证明每次状态变化都不会漏掉答案？

中心结论：先把 nums 放入 set 去重;再遍历 set,只对「num-1 不在 set」的起点向右扩展 num+1、num+2…;每段序列只会被它的最小值启动一次。

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。

在本站主例中，在未排序数组 [100,4,200,1,3,2] 中找最长连续序列长度,要求 O(n)。

算法最终需要得到或观察：最长连续序列 1,2,3,4,长度 4。

逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“哈希记忆表”，明确答案需要观察什么。
2. 2状态只维护 set 快照(已去重)、当前 num、起点测试 num-1、currentLen、maxLen、最长段记录。
3. 3转移每一步按照 先把 nums 放入 set 去重;再遍历 set,只对「num-1 不在 set」的起点向右扩展 num+1、num+2…;每段序列只会被它的最小值启动一次。
4. 4收尾读取 最长连续序列 1,2,3,4,长度 4。，并复核边界与复杂度。

先问未来需要查询什么，再决定 map 的 key 与 value。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：set 快照(已去重)、当前 num、起点测试 num-1、currentLen、maxLen、最长段记录。

给出一个数组，要求找出最长连续序列，输出这个最长的长度。要求时间复杂度为 `O(n)`。 这一题可以先用暴力解决解决，代码见解法三。思路是把每个数都存在 `map` 中，先删去 `map` 中没有前一个数 `nums[i]-1` 也没有后一个数 `nums[i]+1` 的数 `nums[i]`，这种数前后都不连续。然后在 `map` 中找到前一个数 `nums[i]-1` 不存在，但是后一个数 `nums[i]+1` 存在的数，这种数是连续序列的起点，那么不断的往后搜，直到序列“断”了。最后输出最长序列的长度。 这一题最优的解法是解法一，针对每一个 `map` 中不存在的数 `n`，插入进去都做 2 件事情。第一件事，先查看 `n - 1` 和 `n + 1` 是否都存在于 `map` 中，如果都存在，代表存在连续的序列，那么就更新 `left`，`right` 边界。那么 `n` 对应的这个小的子连续序列长度为 `sum = left + right + 1`。第二件事就是更新 `left` 和 `right` 左右边界对应的 `length = sum`。 这一题还可以用并查集解决，见解法二。利用每个数在 `nums` 中的下标，把下标和下标进行 `union()`，具体做法是看前一个数 `nums[i]-1` 和后一个数 `nums[i]+1` 在 `map` 中是否存在，如果存在就 `union()`，最终输出整个并查集中包含最多元素的那个集合的元素总数。

先把 nums 放入 set 去重;再遍历 set,只对「num-1 不在 set」的起点向右扩展 num+1、num+2…;每段序列只会被它的最小值启动一次。

执行过程中持续维护：set 快照(已去重)、当前 num、起点测试 num-1、currentLen、maxLen、最长段记录。

正确性依赖以下不变量：任何连续序列只会从它的最小值开始扩展一次。；非起点 x 一定有 x-1 存在,所以它属于某个更早开始的连续段,不需要再次扩展。；遍历 set 后,每个唯一数字最多作为内层 while 的一部分被访问一次,因此总复杂度 O(n)。

面试时可以压缩为：这题要求 O(n),所以不能排序。我先用 HashSet 去重并支持 O(1) 查询。然后遍历 set 中的每个唯一数字,只有当 num-1 不存在时,num 才是一个连续段的起点,再向右查 num+1、num+2。这样每个连续段只会被它的最小值启动一次,避免重复扩展,整体 O(n)。

落到当前题，执行机制可以压缩为：先把 nums 放入 set 去重;再遍历 set,只对「num-1 不在 set」的起点向右扩展 num+1、num+2…;每段序列只会被它的最小值启动一次。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入在未排序数组 [100,4,200,1,3,2] 中找最长连续序列长度,要求 O(n)。 因为：先把 nums 放入 set 去重;再遍历 set,只对「num-1 不在 set」的起点向右扩展 num+1、num+2…;每段序列只会被它的最小值启动一次。
2. 2建好查找集合把数组装进 set,去重并支持 O(1) 查找。 因为：不能排序(O(n log n)),用 set 才能做到 O(n)。
3. 3从 100 向上扩展,长度 1不断查 x+1, x+2, ... 是否在 set,数出这一段长度。 因为：每个数在「扩展」里最多被访问一次,所以总体仍是 O(n)。
4. 44 是序列起点吗?只从「起点」开始数,避免对同一段序列重复计数。 因为：若 x-1 也在 set,x 会被 x-1 那一段数到;只从起点扩展才保证每个数只被数一次。
5. 5从 200 向上扩展,长度 1不断查 x+1, x+2, ... 是否在 set,数出这一段长度。 因为：每个数在「扩展」里最多被访问一次,所以总体仍是 O(n)。
6. 6从 1 向上扩展,长度 4不断查 x+1, x+2, ... 是否在 set,数出这一段长度。 因为：每个数在「扩展」里最多被访问一次,所以总体仍是 O(n)。
7. 72 是序列起点吗?只从「起点」开始数,避免对同一段序列重复计数。 因为：若 x-1 也在 set,x 会被 x-1 那一段数到;只从起点扩展才保证每个数只被数一次。
8. 8收尾与复杂度最长连续序列 1,2,3,4,长度 4。 因为：时间 O(n) · 空间 O(n)。先把 nums 放入 set 去重;再遍历 set,只对「num-1 不在 set」的起点向右扩展 num+1、num+2…;每段序列只会被它的最小值启动一次。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import (
	"github.com/halfrost/LeetCode-Go/template"
)

// 解法一 map，时间复杂度 O(n)
func longestConsecutive(nums []int) int {
	res, numMap := 0, map[int]int{}
	for _, num := range nums {
		if numMap[num] == 0 {
			left, right, sum := 0, 0, 0
			if numMap[num-1] > 0 {
				left = numMap[num-1]
			} else {
				left = 0
			}
			if numMap[num+1] > 0 {
				right = numMap[num+1]
			} else {
				right = 0
			}
			// sum: length of the sequence n is in
			sum = left + right + 1
			numMap[num] = sum
			// keep track of the max length
			res = max(res, sum)
			// extend the length to the boundary(s) of the sequence
			// will do nothing if n has no neighbors
			numMap[num-left] = sum
			numMap[num+right] = sum
		} else {
			continue
		}
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

// 解法二 并查集
func longestConsecutive1(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	numMap, countMap, lcs, uf := map[int]int{}, map[int]int{}, 0, template.UnionFind{}
	uf.Init(len(nums))
	for i := 0; i < len(nums); i++ {
		countMap[i] = 1
	}
	for i := 0; i < len(nums); i++ {
		if _, ok := numMap[nums[i]]; ok {
			continue
		}
		numMap[nums[i]] = i
		if _, ok := numMap[nums[i]+1]; ok {
			uf.Union(i, numMap[nums[i]+1])
		}
		if _, ok := numMap[nums[i]-1]; ok {
			uf.Union(i, numMap[nums[i]-1])
		}
	}
	for key := range countMap {
		parent := uf.Find(key)
		if parent != key {
			countMap[parent]++
		}
		if countMap[parent] > lcs {
			lcs = countMap[parent]
		}
	}
	return lcs
}

// 解法三 暴力解法，时间复杂度 O(n^2)
func longestConsecutive2(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	numMap, length, tmp, lcs := map[int]bool{}, 0, 0, 0
	for i := 0; i < len(nums); i++ {
		numMap[nums[i]] = true
	}
	for key := range numMap {
		if !numMap[key-1] && !numMap[key+1] {
			delete(numMap, key)
		}
	}
	if len(numMap) == 0 {
		return 1
	}
	for key := range numMap {
		if !numMap[key-1] && numMap[key+1] {
			length, tmp = 1, key+1
			for numMap[tmp] {
				length++
				tmp++
			}
			lcs = max(lcs, length)
		}
	}
	return max(lcs, length)
}

func main() {
    // 1. 主例
    //    输入：mode="longest-consecutive", nums=[100,4,200,1,3,2]
    //    期望：最长连续序列 1,2,3,4,长度 4。
    //
    // 2. 失败 / 未命中
    //    检查：对每个数都向左右扩展会让同一段被段中所有 L 个数各扫一次,退化为 O(n²)。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC1 两数之和；LC49 字母异位词分组
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意在未排序数组 [100,4,200,1,3,2] 中找最长连续序列长度,要求 O(n)。
2. 2重复逐对枚举能够得到答案，但同一个查找会发生许多次；哈希表把已经见过的信息保存成一次查询。
3. 3优化先把 nums 放入 set 去重;再遍历 set,只对「num-1 不在 set」的起点向右扩展 num+1、num+2…;每段序列只会被它的最小值启动一次。
4. 4证明任何连续序列只会从它的最小值开始扩展一次。；非起点 x 一定有 x-1 存在,所以它属于某个更早开始的连续段,不需要再次扩展。；遍历 set 后,每个唯一数字最多作为内层 while 的一部分被访问一次,因此总复杂度 O(n)。
5. 5复杂度时间 O(n)，空间 O(n)