本文共 2129 字，大约阅读时间需要 7 分钟。
This problem is not very intuitive at first glance. However, the final idea should be very self-explanatory. You visit each element in nums, and then find its left and right neighbors and extend the length accordingly. The time complexity is O(n) if we guard from visiting the same element again.
You can implement it using an unordered_set or unordered_map.
The code is as follows. The last one is taken from which includes a nice explanation in the follong answers.
1 // O(n) solution using unordered_set 2 int longestConsecutive(vector & nums) { 3 unordered_set copy(nums.begin(), nums.end()); 4 unordered_set filter; 5 int len = 0; 6 for (int i = 0; i < nums.size(); i++) { 7 if (filter.find(nums[i]) != filter.end()) continue; 8 int l = nums[i] - 1, r = nums[i] + 1; 9 while (copy.find(l) != copy.end()) filter.insert(l--);10 while (copy.find(r) != copy.end()) filter.insert(r++);11 len = max(len, r - l - 1);12 }13 return len;14 }15 16 // O(n) solution using unordered_map17 int longestConsecutive(vector & nums) {18 unordered_map mp;19 int len = 0;20 for (int i = 0; i < nums.size(); i++) {21 if (mp[nums[i]]) continue;22 mp[nums[i]] = 1;23 if (mp.find(nums[i] - 1) != mp.end())24 mp[nums[i]] += mp[nums[i] - 1];25 if (mp.find(nums[i] + 1) != mp.end())26 mp[nums[i]] += mp[nums[i] + 1];27 mp[nums[i] - mp[nums[i] - 1]] = mp[nums[i]]; // left boundary28 mp[nums[i] + mp[nums[i] + 1]] = mp[nums[i]]; // right boundary29 len = max(len, mp[nums[i]]);30 }31 return len;32 }33 34 // O(n) super-concise solution (merging the above cases)35 int longestConsecutive(vector & nums) {36 unordered_map mp;37 int len = 0;38 for (int i = 0; i < nums.size(); i++) {39 if (mp[nums[i]]) continue;40 len = max(len, mp[nums[i]] = mp[nums[i] - mp[nums[i] - 1]] = mp[nums[i] + mp[nums[i] + 1]] = mp[nums[i] - 1] + mp[nums[i] + 1] + 1);41 }42 return len;43 } 转载地址：http://xzzlo.baihongyu.com/