这道题给出一个未排序的整数数组，按照题意最先想到直接做 Arrays.sort(nums) 排序就可以了，但是题目要求 O(n) 的时间复杂度，在 Arrays.sort(nums) 排序中底层逻辑采用的是快排，时间复杂度为 O(nlogn) ，不符合题意

另辟蹊径：

目标：要求数字连续的最长序列，序列本身的元素在数组中原来的位置不一定要连续。

将问题具体化，比如说我们现在就拿着数组中第一个元素 100 ，要想找它所在的数字连续的最长序列，肯定要去看数组中有没有 101，102，103，104 … 然后统计长度。

再将问题抽象化，对于 nums 中的元素 x ，以 x 为起点，不断查找下一个数 x + 1，x + 2， x + 3 …是否存在数组中，统计序列的长度。

有了核心思路，现在看看时间复杂度，遍历数组 nums 每个元素，针对该元素再去遍历整个数组看有没有连续数字，两层 for 循环，时间复杂度为 O(n²) ，不符合要求。这里判断数组中是否存在某个数字，可以采用 Set 数据结构，通过去重与 contains() 方法来判断，可以做到时间复杂度为 O(1)。

除此之外，还有一个可优化的点，我们在遍历 nums 数组中元素时，默认所有元素都是它所在连续数字序列的首位，但这是有冗余的。比如拿本题的实例来说，我们在遍历第一个元素 100 的时候，找它的后续连续数字 101，这没有问题，因为 100 一定是连续数字首位；但是在遍历第二个元素 4 的时候，问题就出现了，它并不是连续数字首位，它的前一位数字 3 也在数组中，那么为什么我们不去遍历到 3 的时候再去找连续数字序列呢？元素 4 的这次判断是不是可以剪枝掉呢？答案是肯定的。包括数字 3 也不是首位，首位是数字 1 ，那么对于数组 nums 中的元素 4、3、2 都可以跳过判断逻辑。

总结来说，我们在找连续数字序列时，数字 x 要做判断，看 x – 1 数字是否在数组中。如果存在，那么剪枝；如果不存在，说明一定是起始点，可以后续查找。

至此时间复杂度为 O(n)。

完整代码：

class Solution {
    public int longestConsecutive(int[] nums) {
        //使用 Set 对数组元素去重
        Set<Integer> numsSet = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            numsSet.add(nums[i]);
        }

        int result = 0;
        //开始遍历 numsSet 元素，找到数字连续的最长序列
        for(Integer num : numsSet){
            //做剪枝操作
            if(numsSet.contains(num - 1)){
                continue;
            }
            //正常进入数字连续序列查询
            int currentNum = num;
            int currentCount = 0;
            while(numsSet.contains(currentNum)){
                currentNum++;
                currentCount++;
            }
            result = Math.max(result, currentCount);
        }
        return result;
    }
}

提到快速排序，手撕一下快排吧

算法流程：

1. 选择一个元素赋给中间变量 temp，默认选择左侧第一个元素，这样左侧第一个元素空了出来；
2. 视角专注右侧：先从最右侧的元素开始依次与 temp 比较大小（采用 while 循环可以一直比较），大于等于 temp 的元素保持不变，右侧 right 索引减一，一旦遇到小于 temp 的元素就可以终止 while 循环，把该元素赋值给步骤 1 中空出来的位置，即 nums[left] = nums[right]；同时左侧 left 索引加一，此时右侧的元素空了出来，与步骤 1 逻辑一样；
3. 视角专注左侧：索引 left 所在的左侧元素开始依次与 temp 比较大小，小于等于 temp 的元素保持不变，左侧 left 索引加一，一旦遇到大于 temp 的元素终止 while 循环，把该元素赋值给步骤 2 中空出来的位置，即 nums[right] = nums[left]；同时右侧 right 索引减一；
4. 依次循环 2,3 步，直至 left == right，完成一轮循环，将 temp 值赋给该索引处，即 nums[left] = temp；并返回该索引 return left；
5. 拿到第 4 步的索引 partPoint 后，此时数组 nums 分成左右两部分 [0, partPoint – 1] 和 [partPoint + 1, nums.length – 1]，再对这两个子数组执行 1,2,3,4 步（递归）。一生二、二生四、四生八，直到子数组只有一个元素则排序完成。

完整代码：

public class test {

    public static void main(String[] args) {

        int[] a = {49, 38, 65, 97, 76, 13, 27, 47};
        quickSort(a, 0, a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }

    }

    //快排算法
    private static void quickSort(int[] nums, int left, int right) {
        int partPoint;
        if(left < right){
            partPoint = partition(nums, left, right);
            quickSort(nums, left, partPoint - 1);
            quickSort(nums, partPoint + 1, right);
        }

    }
    
    // 切割数组
    private static int partition(int[] nums, int left, int right) {
        int temp = nums[left];
        while(left < right){
            //右边视角
            while(left < right && nums[right] >= temp){
                right--;
            }
            if(left < right){
                nums[left] = nums[right];
                left++;
            }

            //左边视角
            while(left < right && nums[left] <= temp){
                left++;
            }
            if(left < right){
                nums[right] = nums[left];
                right--;
            }
        }
        nums[left] = temp;
        return left;
    }

}

输入：

输出：