128. 最长连续序列 - 力扣（LeetCode）

自己的思路

开始的思路是建立一个vector做哈希，下标映射nums元素，值存储以该值为最后一个元素的最长序列。

但这样有很多问题，比如原先1、2、3、5、6、7都有值，此时插入一个4如何更新5、6、7？还有如果nums形如[1, 2 ,3 , 10000]建立vector就会有很多冗余空间浪费

题解的思路

<aside> 💡 重点：只从一条序列中的第一个元素开始计算（即 n - 1 不在哈希表中），其余元素跳过

</aside>

这样的话当拿到一个数字n时，我们只需要考虑 n+1 是否在nums中，这样就解决了自己思路中形如插入4时难以连接两个子序列的问题

由于只需要检测元素是否存在而不需要对其进行映射，所以选择unordered_set容器。同时，题目要求时间复杂度为O(n)，而unordered_set搜索一次的时间复杂度为O(1)，也能满足时间复杂度要求

代码

// unordered_set搜索元素的时间复杂度是O(1)
int longestConsecutive(vector<int>& nums) {
	unordered_set<int> st;
	for (int num : nums)
		st.insert(num);

	int ans = 0;
	for (int num : nums) {
		// 只从一条序列中的第一个元素开始计算（即 n - 1 不在哈希表中），其余元素跳过
		// 这样保证每个元素只会被哈希表搜索一次，减少冗余计算
		if (st.count(num - 1) == 0) {
			int n = num;
			int count = 1;
			while (st.count(++n))
				++count;
			ans = std::max(ans, count);
		}
	}
	return ans;
}