128. 最长连续序列

https://leetcode-cn.com/problems/longest-consecutive-sequence/

优化思路：

1. 暴力法最容易想到，然后对暴力法优化。
2. 发现【1】的“contains()”函数时间复杂度高，根据“查询勤用Hash表的思路”和题目自身的特点，使用HashSet即可。
3. 针对【2】的循环中，如【1,2,3,4,5】的特点，其实遍历了一遍之后，以“2”开头的遍历思路其实与“1”开头的一样，只不过数值加一，因此，提出当前Set中包含当前遍历数字的前驱时，即放弃遍历。

class Solution {
    public int longestConsecutive(int[] nums) {
        // 进一步优化：既然存在大量重复辨别，使用 前驱 来帮助跳过重复
        // 遍历到当前数字时，只要 HsehSet 中的 "当前数字 - 1" 存在，就跳过
        int maxLen = 0;
        // 定义一个 HashSet，保存所有出现的数值
        HashSet<Object> hashSet = new HashSet<>();
        // 遍历一遍所有元素
        for (int num : nums) {
            hashSet.add(num);
        }
        // 遍历数组，以每个元素作为起始点，寻找连续序列
        for (int i = 0; i < nums.length; i++) {
            // 当前元素作为起始点
            int curNum = nums[i];
            // 保存当前连续子序列长度
            int curLen = 1;
            // 只有在当前元素的前驱不存在的情况下，才去进行寻找连续序列的操作
            if (!hashSet.contains(curNum - 1)) {
                // 寻找后续数字
                while (hashSet.contains(curNum + 1)) {
                    curLen++;
                    curNum++;
                }
                maxLen = curLen > maxLen ? curLen : maxLen;
            }
        }
        return maxLen;
    }
}

    public int longestConsecutiveAdvanced(int[] nums) {
        // 暴力法优化：contains 函数的功能交给 HashSet 来执行，降低时间复杂度
        // 思路几乎一样，不过先使用一次遍历来一劳永逸地将数据存入 HashSet，便于后面使用
        int maxLen = 0;
        // 定义一个 HashSet，保存所有出现的数值
        HashSet<Object> hashSet = new HashSet<>();
        // 遍历一遍所有元素
        for (int num : nums) {
            hashSet.add(num);
        }
        // 遍历数组，以每个元素作为起始点，寻找连续序列
        for (int i = 0; i < nums.length; i++) {
            // 当前元素作为起始点
            int curNum = nums[i];
            // 保存当前连续子序列长度
            int curLen = 1;
            // 寻找后续数字
            while (hashSet.contains(curNum + 1)) {
                curLen++;
                curNum++;
            }
            maxLen = curLen > maxLen ? curLen : maxLen;
        }
        return maxLen;
    }

    public int longestConsecutive(int[] nums) {
        // 暴力法：时间复杂度过高
        // 定义一个长度，保持当前最长连续序列的长度
        int maxLen = 0;
        // 遍历数组，以每个元素作为起始点，寻找连续序列
        for (int i = 0; i < nums.length; i++) {
            // 当前元素作为起始点
            int curNum = nums[i];
            // 保存当前连续子序列长度
            int curLen = 1;
            // 寻找后续数字，只有当前 nums 继续包含 [ 当前数 + 1 ]，就继续，同时长度++
            while (contains(nums, curNum + 1)) {
                curLen++;
                curNum++;
            }
            maxLen = curLen > maxLen ? curLen : maxLen;
        }
        return maxLen;
    }
    public boolean contains(int[] nums, int x) {
        // 定义一个方法，用于在数组中寻找某个元素
        for (int num : nums) {
            if (num == x) {
                return true;
            }
        }
        return false;
    }