數(shù)組系列
力扣數(shù)據(jù)結(jié)構(gòu)之數(shù)組-00-概覽
力扣.53 最大子數(shù)組和 maximum-subarray
力扣.128 最長連續(xù)序列 longest-consecutive-sequence
力扣.167 兩數(shù)之和 II two-sum-ii
力扣.170 兩數(shù)之和 III two-sum-iii
力扣.653 兩數(shù)之和 IV two-sum-IV
題目
給定一個未排序的整數(shù)數(shù)組 nums 甘萧，找出數(shù)字連續(xù)的最長序列（不要求序列元素在原數(shù)組中連續(xù)）的長度。
請你設(shè)計并實現(xiàn)時間復(fù)雜度為 O(n) 的算法解決此問題意狠。
示例 1：
輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長數(shù)字連續(xù)序列是 [1, 2, 3, 4]睦番。它的長度為 4命黔。
示例 2：
輸入：nums = [0,3,7,2,5,8,4,6,0,1]
輸出：9
提示：
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
v1-基本解法
思路
在經(jīng)歷過 T53 的洗禮之后厘灼，看到這一題感覺很親切义图。
因為連續(xù)相對而言比較好考慮一些艇棕，不過還是有一點點坑：
整體思路如下：
1）數(shù)組排序
2）判斷當前 nums[i] - nums[i-1]蝌戒。用 maxLen 計算全局最優(yōu)串塑，tempLen 保存局部最優(yōu)
a. 等于 0沼琉，則兩個數(shù)字相等。依然連續(xù)桩匪，但是 tempLen 長度不變
b. 等于 1打瘪，數(shù)字嚴格連續(xù)，tempLen++
c. 其他 連續(xù)性中斷 tempLen=1
當然等于0的場景要看錯誤的測試用例才能知道傻昙，題目描述的并不夠清晰闺骚。
比如把這一題改成嚴格連續(xù)，那考慮條件就要調(diào)整一下妆档。
實現(xiàn)
public int longestConsecutive(int[] nums) {
if(nums.length == 0) {
return 0;
}
// 排序
Arrays.sort(nums);
int maxLen = 1;
int tempLen = 1;
// 對于連續(xù)的定義是什么僻爽？
for(int i = 1; i < nums.length; i++) {
int num = nums[i];
int pre = nums[i-1];
if(num - pre == 1) {
tempLen++;
} else {
// 斷開
tempLen = 1;
}
maxLen = Math.max(maxLen, tempLen);
}
return maxLen;
}
效果
13ms 93.27%
小結(jié)
這種 one-pass 的需要理解清楚題目的意思，解決一些邊界和特殊的場景問題贾惦。
想到了就不難胸梆。
