题解 | #连续的牛群标签序列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param tag int整型一维数组
     * @return int整型
     */
    public int longestConsecutive (int[] tag) {
        // write code here
        if (tag == null || tag.length == 0) {
            return 0;
        }

        Set<Integer> numSet = new HashSet<>();
        for (int num : tag) {
            numSet.add(num);
        }

        int longestStreak = 0;

        for (int num : numSet) {
            if (!numSet.contains(num - 1)) { // Start of a sequence
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

知识点：

使用 HashSet 可以实现快速查找，它的查找操作时间复杂度是 O(1)。

利用开头元素和向后查找，可以在 O(n) 时间复杂度内解决连续子序列问题。

解题思路：

使用了一个 HashSet 来存储数组中的所有元素，以便快速地查找一个元素是否存在。然后，我们遍历数组中的每个元素，对于每个元素，我们检查是否存在 num - 1，如果不存在，说明它是一个序列的开头。

然后，我们从这个开头元素开始，通过不断向后查找，统计连续递增的序列长度。我们使用一个 currentNum 变量来迭代序列中的元素，并使用 currentStreak 变量来记录当前序列的长度。

在每一次迭代中，我们检查 currentNum + 1 是否存在于 HashSet 中，如果存在，就说明序列可以继续延伸，我们增加 currentNum 和 currentStreak。当无法继续延伸时，我们将 currentStreak 与 longestStreak 进行比较，取较大值。

最后，我们得到了最长的连续递增序列的长度。