跳转至

最长连续序列

最后更新：2024-05-10-22

链接：https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked

题目描述

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

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

题目示例

输入： nums = [100,4,200,1,3,2]

输出： 4

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

输入： nums = [0,3,7,2,5,8,4,6,0,1]

输出： 9

提示：

  • \(0 <= nums.length <= 10^5\)
  • \(-10^9 <= nums[i] <= 10^9\)

题解

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

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

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

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

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

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

  • 首先去重
  • 然后排序
  • 依次遍历，找到满足的最长子数组，返回其长度。
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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 := 0
    for 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/2
	    if valDiff > indexDiff && indexDiff != 0 {
		    curMaxDiff = curMaxDiff / 2
		    end = end - curMaxDiff
		    continue
	    }

	    // 索引差值 > 数值差值，这种不可能存在，因为已经去重了
	    // 索引差值 = 数值差值，后面可能还有满足条件的，继续找
	    if valDiff == indexDiff {
		    // 刷新最大值
		    if longestStreak > valDiff {
			    break
		    }

		    longestStreak = valDiff
		    // end后移curMaxDiff/2
		    curMaxDiff = curMaxDiff / 2
		    end = end + curMaxDiff
		    continue
	    }
    }

    return longestStreak
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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 := 0
    for num := range numTemp {
	    if num < len(numTemp)-1 && numTemp[num]+1 == numTemp[num+1] {
		    currentNum := num
		    currentStreak := 1
		    for currentNum < len(numTemp)-1 && numTemp[currentNum]+1 == numTemp[currentNum+1] {
			    currentNum++
			    currentStreak++
		    }
		    if longestStreak < currentStreak {
			    longestStreak = currentStreak
		    }
	    }
    }
    return longestStreak
}