力扣100热题[哈希]：最长连续序列

原题：128. 最长连续序列

题解：

官方题解：. - 力扣（LeetCode）题解，最长连续序列 ：哈希表

官方解题思路是先去重，然后判断模板长度的数值是否存在，存在就刷新，最终找到最大值。

这里我自己研究了下，实际也是暴力解法。纯暴力解法会超时，这里利用了二分法查找的理念

• 首先去重
• 然后排序
• 固定begin，然后找最大的end，返回使用二分法理念进行查找
• 依次遍历，在已经找到的最大值，返回

自己尝试了下，部分通过，有些边界值不太好控制，而且输入里面有负数，也不太好计算。

还有一种解题方法，就是在官方题解上做个变化，

• 首先去重
• 然后排序
• 依次遍历，找到满足的最长子数组，返回其长度。

代码：

func longestConsecutive(nums []int) int {// 如果数组为空，或者只有一个元素，直接返回数组长度if len(nums) <= 1 {return len(nums)}// 去重numSet := map[int]bool{}for _, num := range nums {numSet[num] = true}// 排序numTemp := make([]int, 0)for num := range numSet {numTemp = append(numTemp, num)}sort.Ints(numTemp)// fmt.Printf("numTemp %v\n", numTemp)// 暴力解法longestStreak := 0for begin := range numTemp {// 当剩余的个数，小于当前最大长度，则后面不可能有满足条件的更大的值，返回if begin+longestStreak > len(numTemp) {return longestStreak + 1}temp := BinarySearchMatch(numTemp, begin, longestStreak)if longestStreak < temp {longestStreak = temp}}return longestStreak + 1
}func BinarySearchMatch(numTemp []int, begin, cur int) int {longestStreak := cur// 当前最大可用差值curMaxDiff := len(numTemp) - begin - 1// 使用二分法的理念，查询满足条件的数据for end := len(numTemp) - 1; end > begin; {// fmt.Printf("begin %v, end %v, curMaxDiff %v\n", begin, end, curMaxDiff)// 索引差值超过最大值，返回，end超过数组范围，返回if curMaxDiff >= len(numTemp) || end >= len(numTemp) {break}// 差值为0时，有可能会遗漏一个，判断end的下一个是否满足条件if curMaxDiff == 0 {if end < len(numTemp)-1 && numTemp[end+1]-numTemp[begin] == end+1-begin {longestStreak = end + 1 - begin}if end > begin && numTemp[end-1]-numTemp[begin] == end-1-begin {longestStreak = end - 1 - begin}if end > begin && numTemp[end]-numTemp[begin] == end-begin {longestStreak = end - begin}break}// 数值差值valDiff := numTemp[end] - numTemp[begin]// 索引差值indexDiff := end - begin// 二分法找到合适的索引end// 索引差值 < 数值差值，数值太大了，中间有不连续的，往前移动curMaxDiff/2if valDiff > indexDiff && indexDiff != 0 {curMaxDiff = curMaxDiff / 2end = end - curMaxDiffcontinue}// 索引差值 > 数值差值，这种不可能存在，因为已经去重了// 索引差值 = 数值差值，后面可能还有满足条件的，继续找if valDiff == indexDiff {// 刷新最大值if longestStreak > valDiff {break}longestStreak = valDiff// end后移curMaxDiff/2curMaxDiff = curMaxDiff / 2end = end + curMaxDiffcontinue}}return longestStreak
}

第二种方法

func longestConsecutive(nums []int) int {// 如果数组为空，或者只有一个元素，直接返回数组长度if len(nums) <= 1 {return len(nums)}// 去重numSet := map[int]bool{}for _, num := range nums {numSet[num] = true}// 排序numTemp := make([]int, 0)for num := range numSet {numTemp = append(numTemp, num)}sort.Ints(numTemp)//fmt.Printf("numTemp %v\n", numTemp)// 暴力解法longestStreak := 0for num := range numTemp {if num < len(numTemp)-1 && numTemp[num]+1 == numTemp[num+1] {currentNum := numcurrentStreak := 1for currentNum < len(numTemp)-1 && numTemp[currentNum]+1 == numTemp[currentNum+1] {currentNum++currentStreak++}if longestStreak < currentStreak {longestStreak = currentStreak}}}return longestStreak
}