/**
* 【數(shù)組中最長(zhǎng)連續(xù)子數(shù)組】
* 給定一個(gè)未排序的整數(shù)數(shù)組 nums 垛耳，找出數(shù)字連續(xù)的最長(zhǎng)序列（不要求序列元素在原數(shù)組中連續(xù)）的長(zhǎng)度萨赁。
* 請(qǐng)你設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 的算法解決此問題踪旷。
* 鏈接：https://leetcode-cn.com/problems/longest-consecutive-sequence
* <p>
* 輸入：nums = [100,4,200,1,3,2]
* 輸出：4
* 解釋：最長(zhǎng)數(shù)字連續(xù)序列是 [1, 2, 3, 4]。它的長(zhǎng)度為 4。
* <p>
* 分析：
* 1.用hash表降低復(fù)雜度
* 2.[1,2,3]中，如果已經(jīng)對(duì)1做了longestConsecutive操作，就沒必要對(duì)2和3做longestConsecutive操作：可以降低復(fù)雜度奢讨。
* 判定依據(jù)：map.get(n-1)是否存在
*
* @author xuan
* @create 2021-10-18 16:42
**/
public class ZuiChangLianXuXuLie {
public static void main(String[] args) {
int[] arr = {100, 4, 200, 1, 3, 2};
System.out.println(longestConsecutive(arr));
}
public static int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
//set去重
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
//開始查找最長(zhǎng)數(shù)字連續(xù)序列
int longest = 0;
for (Integer val : set) {
int innerLongest = 1;
if (set.contains(val - 1)) {
//小團(tuán)伙的非頭元素：跳過
continue;
}
//找到了小團(tuán)伙的頭元素，開始猜測(cè)小團(tuán)伙長(zhǎng)度
while (set.contains(++val)) {
innerLongest++;
}
longest = longest > innerLongest ? longest : innerLongest;
}
return longest;
}
}
數(shù)組中最長(zhǎng)連續(xù)子數(shù)組
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門鞭光，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人泞遗，你說我怎么就攤上這事惰许。” “怎么了史辙？”我有些...
- 文/不壞的土叔 我叫張陵汹买，是天一觀的道長(zhǎng)。 經(jīng)常有香客問我聊倔，道長(zhǎng)晦毙，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任耙蔑，我火速辦了婚禮见妒，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘甸陌。我一直安慰自己须揣，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布邀层。 她就那樣靜靜地躺著返敬，像睡著了一般。 火紅的嫁衣襯著肌膚如雪寥院。 梳的紋絲不亂的頭發(fā)上劲赠，一...
- 文/蒼蘭香墨 我猛地睜開眼，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼最铁！你這毒婦竟也來了讯赏？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬榮一對(duì)情侶失蹤冷尉，失蹤者是張志新（化名）和其女友劉穎漱挎，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體雀哨，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡磕谅，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了雾棺。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片膊夹。...
- 正文 年R本政府宣布宏榕，位于F島的核電站，受9級(jí)特大地震影響侵佃，放射性物質(zhì)發(fā)生泄漏麻昼。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一馋辈、第九天 我趴在偏房一處隱蔽的房頂上張望抚芦。 院中可真熱鬧，春花似錦迈螟、人聲如沸叉抡。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽褥民。三九已至，卻和暖如春洗搂，著一層夾襖步出監(jiān)牢的瞬間消返，已是汗流浹背载弄。 一陣腳步聲響...
- 正文 我出身青樓，卻偏偏與公主長(zhǎng)得像倡勇，于是被迫代替她去往敵國(guó)和親逞刷。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 16宿命：用概率思維提高你的勝算 以前的我是風(fēng)險(xiǎn)厭惡者妻熊，不喜歡去冒險(xiǎn)夸浅，但是人生放棄了冒險(xiǎn)，也就放棄了無數(shù)的可能扔役。 ...
- 公元：2019年11月28日19時(shí)42分農(nóng)歷：二零一九年 十一月 初三日 戌時(shí)干支：己亥乙亥己巳甲戌當(dāng)月節(jié)氣：立冬...
- 今天上午陪老媽看病题篷，下午健身房跑步，晚上想想今天還沒有斷舍離厅目，馬上做，衣架和旁邊的的布衣架法严，一看亂亂损敷，又想想自己是...
