.NET技术栈

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

输入: [100, 4, 200, 1, 3, 2]
输出: 4

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

原文链接: https://leetcode-cn.com/problems/longest-consecutive-sequence/

解题

• 用一个字典存数组中每个数字的当前连续最长长度
• 如果已经遍历过的则跳过
• 若从未遍历过
  • 取左右相邻的数字
  • 当前最大即为 左边存的值 + 右边存的值 + 1
  • 更新两端的值(因为在循环中只会用到两端的值)

static int LongestConsecutive(int[] nums)
{
    if (nums.Length <= 1) return nums.Length;
    var dict = new Dictionary<int,int>();
    var max = 1;
    for (var i = 0; i < nums.Length; i++)
    {
        var num = nums[i];
        if (!dict.ContainsKey(num))
        {
            var left = num - 1;
            var leftValue = 0;
            
            var right = num + 1;
            var rightValue = 0;
            
            if (dict.ContainsKey(left)) //取左侧存值
                leftValue = dict[left];
            
            if (dict.ContainsKey(right)) //取右侧存值
                rightValue = dict[right];

            var value = leftValue + rightValue + 1;
            if (value > max) max = value;
            dict[num] = value;
            if (leftValue>0)
                dict[num-leftValue]=value; //更新最左端的值
            if (rightValue>0)
                dict[num+rightValue] = value; //更新最右段的值
        }
    }
	return max;
}

执行结果