128.M 最长连续序列

Problem: 128. 最长连续序列

思路

最简单的思路是排序，排序后很容易判断最长连续序列的长度是多少，但是不符合时间复杂度要求。

所以考虑首先用map存储序列中的数字，然后对于每个数字num，不断判断num+1是否在map中，这样产生的问题是会有很多重复的判断。比如序列是1,2,3,4,5,6，那么可能2、3、4、5、6会被重复判断多次。

结合排序的思路来看，对于每个连续序列，我们都希望从序列中最小的数字开始触发判断，因此，我们可以增加一个逻辑，如果对于某个数字num，如果num-1也存在于序列中，则num不触发判断。通过这种方式可以把时间复杂度降低到O(N)

Code

func longestConsecutive(nums []int) int {
	numSet := map[int]bool{}
	for _, num := range nums {
		numSet[num] = true
	}

	maxCount := 0
	for _, num := range nums {
		if !numSet[num-1] {
			curCount := 0
			for numSet[num] {
				curCount++
				num++
			}

			if curCount > maxCount {
				maxCount = curCount
			}
		}
	}

	return maxCount
}