LeetCode算法题目：Longest Consecutive Sequence

题目：

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. Your algorithm should run in O(n) complexity.

---

分析：

本题目要求复杂度为O(n)，而元素的序列又是无序的，故想到采用hash表，牺牲空间换取时间。 定义一个unordered_map <int,bool> used 哈希表，使用其bool值记录元素是否被记录， 且以该>元素为中心在hash表中查找与其值相邻的元素，直到不连续，记录下长度。

---

代码实现：

class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_map<int ,bool> used; for (auto i : nums) { nums[i]=false; } int longest=0; for(auto i: nums) { if(nums[i]) continue; int length=1; used[i]=true; for(int j=i+1;used.find(j)!=used.end();j++) { nums[j]=true; length++; } for(int j=i-1;used.find(j)!=used.end();j--) { nums[j]=true; length++; } longest=max(longest,length); } return longest; } };