128. 最长连续序列

题意：

解题思路：

思路：时间复杂度主要是排序，O(nlgn)；空间复杂度O(1)
1. 排序，得到连续序列的数字；
2. 从前往后扫描一遍数组，记录差值为1的最大长度；
3. 当差值不为1的时候，更新最大长度，然后以下一个元素为起点，重新计算长度；

PHP代码实现：

class Solution {
    function longestConsecutive($nums) {
       // return $this->longestConsecutive1($nums);
        if (count($nums) == 0) return 0;
        sort($nums);
        $res = 1;
        $curStreak = 1;
        for ($i = 1; $i < count($nums); $i++) {
            if ($nums[$i] != $nums[$i - 1]) {
                if ($nums[$i] == $nums[$i - 1] + 1) {
                    ++$curStreak;
                } else {
                    $res = max($res, $curStreak);
                    $curStreak = 1;
                }
            }
        }
        return max($res, $curStreak);
    }
    function longestConsecutive1($nums) {
        if (empty($nums) || count($nums) == 0) return 0;
        sort($nums);
        $max = $p = 0;
        while ($p < count($nums)) {
            $len = 1;
            while ($p < count($nums) - 1) {
                if ($nums[$p + 1] - $nums[$p] > 1) break;
                if ($nums[$p + 1] - $nums[$p] == 1) ++$len;
                ++$p;
            }
            $max = max($max, $len);
            ++$p;
        }
        return $max;
    }
    function longestConsecutive2($nums) {
        if (count($nums) == 0) return 0;
        $res = 0;
        foreach($nums as $num) {
            $curNum = $num;
            $curStreak = 1;
            while ($this->arrayContains($nums, $curNum + 1)) {
                ++$curNum;
                ++$curStreak;
            }
            $res = max($res, $curStreak);
        }
        return $res;
    }
    function arrayContains($arr, $num) {
        //return in_array($num, $arr);
        for ($i = 0; $i < count($arr); $i ++) {
            if ($arr[$i] == $num) return true;
        }
        return false;
    }
}

GO代码实现：

func longestConsecutive(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    sort.Ints(nums)
    res, curStreak := 1, 1
    for i := 1; i < len(nums); i++ {
        if nums[i-1] == nums[i] {
            continue
        }
        if nums[i-1] + 1 == nums[i] {
            curStreak++
        } else {
            curStreak = 1
        }
        if curStreak > res {
            res = curStreak
        }
    }
    return res
}