longest-consecutive-sequence

题目描述

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)

题解

从最小的开始往后找。为了去重并把搜索降到O(1)，使用unordered_set。

int longestConsecutive(vector<int>& nums) {
	unordered_set<int> s;
	s.insert(std::begin(nums), std::end(nums));
	int res = 0;
	for (int num : s)
	{
		if (!s.count(num - 1))
		{
			int cur = num;
			int len = 1;
			while (s.count(cur + 1))
			{
				cur++;
				len++;
			}
			res = len > res ? len : res;
		}
	}
	return res;
}