最長連續列
給定一個未排序的整數數組 nums ，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。
請你設計并實現時間復雜度為 O(n) 的算法解決此問題。
輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長數字連續序列是 [1, 2, 3, 4]。它的長度為 4。
輸入：nums = [0,3,7,2,5,8,4,6,0,1]
輸出：9
輸入：nums = [1,0,1,2]
輸出：3
首先這道題，第一眼看到就覺得應該使用Set來解決。為什么呢？首先第一個需要使用set來去重，第二個set可以根據從contains來查找元素。
OK，那我們就先把元素存到set里
Set<Integer> set = new HashSet<>();
for(Integer num : nums){set.add(num);
}
之后呢？題目說復雜度O(n)，所以呢排序不行，那只能另辟蹊徑了。
題目要求找出最大的連續長度，那么我們是不是要想辦法找到他的起點。但是呢又有一個問題，如果不同元素直接差值很大呢，比如400 301 302 -500。這樣不管是說我們先找到最小元素然后去逐步+1，還是第一個元素來計算都很耗時。
那怎么辦呢？我們可以采用直接計算的方法。
起點 x 必然滿足 x-1 不在集合中，所以遍歷集合中的每個元素 x，僅當 x 是起點時（!set.contains(x-1)），才嘗試擴展序列。
這個起點是一個臨時起點，并不是說他一定是整個集合的起點。比如400 300 301。400-1必然是找不到，但不能說400是整體的起點
從起點 x 開始，依次檢查 x+1, x+2, … 是否存在于集合，直到無法繼續。序列長度就為y - x。保存每次查找的結果，最后使用最長的鏈路
for(x : set){//如果還能找到更小的，那就先不使用，去set里找下一個元素if(set.contains(x-1){continue;}//如果當前這個數x，找不到x-1的了，那就先用x來查int y = x + 1;//如果有x+1的數，那就用y記錄下來while(set.contains(y)){y++;}//一次次的循環， 直到找到最大的y-xans = Math.max(ans,y-x);
}
題解：
class Solution {public int longestConsecutive(int[] nums) {Set<Integer> set = new HashSet<>();for(Integer num : nums){set.add(num);}int ans = 0;//假設set里是5 4 3 2 1 0for(Integer x : set){//如果還能找到更小的，那就直接退出if(set.contains(x - 1)){continue;}//如果當前這個數x，找不到x-1的了，那就先用x來查int y = x + 1;//如果有x+1的數，那就用y記錄下來while(set.contains(y)){y++;}//一次次的循環， 知道找到最大的y-xans = Math.max(ans,y-x);}return ans;}
}
用最少數量的箭引爆氣球
有一些球形氣球貼在一堵用 XY 平面表示的墻面上。墻面上的氣球記錄在整數數組 points ，其中points[i] = [xstart, xend] 表示水平直徑在 xstart 和 xend之間的氣球。你不知道氣球的確切 y 坐標。
一支弓箭可以沿著 x 軸從不同點 完全垂直 地射出。在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 xstart，xend， 且滿足 xstart ≤ x ≤ xend，則該氣球會被 引爆 。可以射出的弓箭的數量 沒有限制 。 弓箭一旦被射出之后，可以無限地前進。
給你一個數組 points ，返回引爆所有氣球所必須射出的 最小 弓箭數 。
?輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：氣球可以用2支箭來爆破:
-在x = 6處射出箭，擊破氣球[2,8]和[1,6]。
-在x = 11處發射箭，擊破氣球[10,16]和[7,12]。
?輸入：points = [[1,2],[3,4],[5,6],[7,8]]
輸出：4
解釋：每個氣球需要射出一支箭，總共需要4支箭。
輸入：points = [[1,2],[2,3],[3,4],[4,5]]
輸出：2
解釋：氣球可以用2支箭來爆破:
- 在x = 2處發射箭，擊破氣球[1,2]和[2,3]。
- 在x = 4處射出箭，擊破氣球[3,4]和[4,5]。
首先看到這題，我最初想的是不斷計算兩個節點之間是否覆蓋，太過于復雜
后來看到題解后才想到可以用排序的方法來計算是否覆蓋
按右端點進行排序后，每次在右端點處射箭，就可以覆蓋掉所有左端點<=當前右端點的氣球。射在右端點能最大化的覆蓋重疊的氣球。
若當前氣球的左端>上支箭矢的位置（上一個范圍的右端點），表明需要新加一支箭，并更新當前箭的位置為當前氣球的右端點。
否則則表明，當前氣球被覆蓋，無需處理
首先我們對所有的坐標進行排序（以end坐標為值計算）
Arrays.sort(points,(a,b) -> Integer.compare(a[1],b[1]));
接下來只需要判斷，下一個坐標的左側，是否大于我們這個坐標的右側即可判斷出是否覆蓋。如果不覆蓋則箭數+1
?int end = points[0][1]; //先定義出初始的end坐標，排序后的第一個元素的右側。for(int i = 1; i < points.length; i++){if(points[i][0] > end){ //當前元素的左側，大于end的右側arrows++;end = points[i][1]; }//注意，如果當前元素在我們end的范圍內，end也不需要更新。因為如果更新，那么我們第一個節點就會無法覆蓋到。
}
解：
class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points,(a,b) -> Integer.compare(a[1],b[1]));int arrows = 1;int end = points[0][1];for(int i = 1; i < points.length; i++){if(points[i][0] > end){arrows++;end = points[i][1]; }}return arrows;}
}
