128.最长连续序列，集合，排序

linwt · linwt · commit d8d23d99ccd0 · 2022-04-16T17:53:01.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -56,6 +56,7 @@
 122. 买卖股票的最佳时机 II
 123. 买卖股票的最佳时机 III
 124. 二叉树中的最大路径和
+128. 最长连续序列
 129. 求根节点到叶节点数字之和
 130. 被围绕的区域
 131. 分割回文串
diff --git a/leetcode_Java/DoneType.txt b/leetcode_Java/DoneType.txt
@@ -147,6 +147,7 @@
 56. 合并区间
 75. 颜色分类
 88. 合并两个有序数组
+128. 最长连续序列
 136. 只出现一次的数字
 169. 多数元素
 215. 数组中的第K个最大元素
diff --git a/leetcode_Java/Solution0128.java b/leetcode_Java/Solution0128.java
@@ -0,0 +1,71 @@
+// 128. 最长连续序列
+
+
+/*
+集合：
+1、集合存放去重元素
+2、遍历元素
+  1）元素前值存在集合中则跳过，因为当前元素会被前值计算统计出更长的长度，即只从序列的起点开始计算才是最长的
+  2）记录当前元素和当前长度，当元素后值存在集合中，则更新当前元素和当前长度
+  3）比较比记录最长长度
+  4）优化，最长长度大于数组长度一半时，后面的元素就不用判断了
+    因为如果剩余元素不属于这个序列那么长度小于数组长度一半
+    如果属于这个序列，那么序列起点已经计算了，当前就是最长了
+
+  √：计算长度  x：跳过
+  100  4  200  1  3  2
+   √   x   √   √  x  x
+ */
+class Solution {
+    public int longestConsecutive(int[] nums) {
+        Set<Integer> set = new HashSet<>();
+        for (int num : nums) {
+            set.add(num);
+        }
+        int res = 0;
+        for (int num : nums) {
+            if (set.contains(num - 1)) {
+                continue;
+            }
+            int curNum = num;
+            int curLen = 1;
+            while (set.contains(curNum + 1)) {
+                curNum += 1;
+                curLen += 1;
+            }
+            res = Math.max(res, curLen);
+            if (res > n / 2) {
+                break;
+            }
+        }
+        return res;
+    }
+}
+
+
+/*
+排序：
+1、数组排序
+2、遍历统计连续序列长度，记录最长长度
+ */
+class Solution {
+    public int longestConsecutive(int[] nums) {
+        Arrays.sort(nums);
+        int n = nums.length;
+        if (n < 2) {
+            return n;
+        }
+        int res = 1, curLen = 1;
+        for (int i = 1; i < n; i++) {
+            if (nums[i] == nums[i - 1] + 1) {
+                curLen += 1;
+                res = Math.max(res, curLen);
+            } else if (nums[i] == nums[i - 1]) {
+                continue;
+            } else {
+                curLen = 1;
+            }
+        }
+        return res;
+    }
+}
