LeetCode 128.最长连续序列

题目

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

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

示例

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

题目链接

题目分析

集合法

题目要求我们的时间复杂度是O(n)，由于set中查找的时间复杂度是常数级，所以我们采用集合法解决。大致思路是：遍历原数组nums，在集合中寻找nums[i] - 1，如果存在，则说明nums[i]不是起点；若不存在，则说明nums[i]是一个起点，在集合中不断寻找当前数字自增1，直到找不到为之，更新长度。

set<int> s(nums.begin(), nums.end());
for (auto n : nums) {
    int temp = 1;
    if (s.count(n - 1)) continue;
    else {
        while ( s.count(n + 1) ) {
            n++;
            temp++;
        }
        res = temp > res ? temp : res;
    }
}

题目解答

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        set<int> s(nums.begin(), nums.end());
        int maxlen = 1;
        for (auto n : nums) {
            int temp = 1;
            if (s.count(n - 1)) {
                continue;
            }else {
                int t = n;
                while (s.count(t + 1)) {
                    temp++;
                    t++;
                }
                maxlen = temp > maxlen ? temp : maxlen;
            }
        }

        return maxlen;
    }
};