最长连续序列

1. 题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

2. 思路

1. 思路一
   • 先排序
   • 遍历数组，统计相邻元素差值为1的个数
2. 思路二
   • 遍历一遍放入set中
   • 再遍历一遍，查看n-1是否再set中

3. 实现

3.1. 排序

import "sort"

func longestConsecutive(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	sort.Ints(nums)

	maxCount := 1
	count := 1
	for i := 0; i < len(nums)-1; i++ {
		diff := nums[i+1] - nums[i]
		if diff <= 1 {
			count += diff
		} else {
			count = 1
		}
		maxCount = max(count, maxCount)
	}

	return maxCount
}

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

    return b
}

3.2. map

func longestConsecutive2(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	m := make(map[int]bool, 0)
	for _, num := range nums {
		m[num] = true
	}

	maxCount := 0
	for num := range m {
		//去重，只统计最小的
		if m[num-1] {
			continue
		}

		currentCount := 1
		currentNum := num
		for m[currentNum+1] {
			currentNum++
			currentCount++
		}
		maxCount = Max(currentCount, maxCount)
	}

	return maxCount
}

4. 参考

• 最长连续序列 - 最长连续序列 - 力扣（LeetCode）
• 最长递增子序列.md