目录
128.最长连续序列
228.汇总区间
56.合并区间
57.插入区间
452.用最少数量的箭引爆气球
128.最长连续序列
题意：
给定一个未排序的整数数组
nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为
O(n)的算法解决此问题。
【输入样例】
nums = [100,4,200,1,3,2]
【输出样例】
4
解释：最长数字连续序列是[1,2,3,4]
解题思路：哈希表
1. 使用set，set不包含重复元素；因此我们先将nums中的元素存入到set中，实现一个去重效果。
2. 遍历set，当一个数num的前一位数num-1不在数组中时，表示它可能是连续序列的第一位，持续遍历看他的下一位num+1是否在集合中，如果存在统计长度，直至找不到。
class Solution {public int longestConsecutive(int[] nums) {int count = 0;Set<Integer> numSet = new HashSet<>();for(int num : nums){numSet.add(num);}int tempCount;for(int num : numSet){if(!numSet.contains(num-1)){tempCount = 1;//第一个数while(numSet.contains(++num)){++tempCount;//继续查找}count = Math.max(count,tempCount);}}return count;}
}时间： 击败了84.51%
内存： 击败了89.54%
228.汇总区间
题意：
给定一个 无重复元素 的 有序 整数数组
nums。返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，
nums的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于nums的数字x。列表中的每个区间范围
[a,b]应该按如下格式输出：
"a->b"，如果a != b"a"，如果a == b
【输入样例】
nums = [0，1，2，4，5，7]
【输出样例】
["0->2","4->5","7"]
解题思路：枚举
class Solution {public List<String> summaryRanges(int[] nums) {List<String> list = new ArrayList<>();if(nums.length == 0){return list;}if(nums.length == 1){list.add(String.valueOf(nums[0]));return list;}int i=0;while(i < nums.length){int low = i;++i;while(i<nums.length && nums[i] == nums[i-1]+1){++i;}int high = i-1;String str;if(low == high){str = String.valueOf(nums[low]);}else{str = nums[low]+"->"+nums[high];}list.add(str);}return list;}
}时间： 击败了51.34%
内存： 击败了16.07%
56.合并区间
题意：
以数组
intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
【输入样例】
intervals = [[1,3],[2,6],[8,10],[15,18]]
【输出样例】
[[1,6],[8,10],[15,18]]
解题思路：排序+枚举判断
1.首先，按照给出的二维数组的左区间进行升序排序
2.枚举判断，变量leftBound和rightBound记录当前的左边界和右边界；枚举，如果下一个区间的左边界小于当前的rightBound，证明两个区间可以合并在一起，修改右边界（不是盲目的修改，要修改成较大值，如(1,6),(2,4),直接修改会变成(1,4)，所以要判断）；如果下一个区间的左边界大于rightBound，证明当前的区间没法合并了，添加到数组中。
class Solution {public int[][] merge(int[][] intervals) {List<int[]> res = new ArrayList<>(); //按照左边界排序Arrays.sort(intervals, (x,y)-> Integer.compare(x[0],y[0]));//initial start 是最小左边界int leftBound = intervals[0][0];int rightBound = intervals[0][1];//右边界for(int i=1;i< intervals.length;++i){//如果左边界大于上一个有边界if(intervals[i][0] > rightBound){//加入区间，更新start，加入的是上一个区间res.add(new int[]{leftBound,rightBound});leftBound = intervals[i][0];rightBound = intervals[i][1];}else{//更新右边界rightBound = Math.max(rightBound, intervals[i][1]);}}res.add(new int[]{leftBound,rightBound});return res.toArray(new int[res.size()][]);}
}时间： 击败了80.99%
内存： 击败了92.51%
57.插入区间
题意：
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
【输入样例】
intervals = [[1,3],[6,9]], newInterval = [2,5]
【输出样例】
[[1,5],[6,9]]
解题思路：与上一题类似，但是这一题不需要排序
枚举原区间，考虑四种情况：
1. 当原区间第i个元素的右边界小于插入区间的左边界时，直接插入原区间第i个元素；
2.当原区间第i个元素的左边界大于插入区间的右边界时，插入新区间，并标注已经插入，后续判断到此情况时直接添加原区间的元素；
3.第三种情况时除了1，2外的情形，代表原区间第i个元素与插入区间有重叠，通过判断两个区间的最大值和最小值来更新左右区间。
4. 最后一种情况时原区间已经遍历完毕后，新区间还没插入，直接插入到最后。
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {boolean isInsert = false;//是否已经插入List<int[]> list = new ArrayList<>();int leftBounds = newInterval[0];//新区间的左边界int rightBounds = newInterval[1];//新区间的右边界for(int i=0;i<intervals.length;++i){if(intervals[i][0] > rightBounds){if(!isInsert){list.add(new int[]{leftBounds,rightBounds});isInsert = true;}list.add(new int[]{intervals[i][0],intervals[i][1]});}else if(intervals[i][1] < leftBounds){//在插入区间的左侧list.add(new int[]{intervals[i][0],intervals[i][1]});}else{//有交集，要合并区间leftBounds = Math.min(leftBounds,intervals[i][0]);rightBounds = Math.max(rightBounds,intervals[i][1]);}}//如果遍历完还没有插入，添加到最后if(!isInsert){list.add(new int[]{leftBounds,rightBounds});}return list.toArray(new int[list.size()][]);}
}时间： 击败了97.50%
内存： 击败了67.95%
452.用最少数量的箭引爆气球
题意：
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组
points，其中points[i] = [xstart, xend]表示水平直径在xstart和xend之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标
x处射出一支箭，若有一个气球的直径的开始和结束坐标为xstart，xend， 且满足xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。给你一个数组
points，返回引爆所有气球所必须射出的 最小 弓箭数 。提示:
1 <= points.length <= 105points[i].length == 2-231 <= xstart < xend <= 231 - 1
【输入样例】
points = [[10,16],[2,8],[1,6],[7,12]]
【输出样例】
2
解题思路：与56.合并区间类似，区别是现在更新右边界的时候，要按小的来。
class Solution {public int findMinArrowShots(int[][] points) { //按照左边界排序Arrays.sort(points, (x,y)-> Integer.compare(x[0],y[0]));int result = 1;for(int i=1;i< points.length;++i){//如果左边界大于上一个有边界if(points[i][0] > points[i-1][1]){//加入区间，更新start，加入的是上一个区间++result;}else{//更新右边界points[i][1] = Math.min(points[i-1][1], points[i][1]);}}// int result = res.size;return result;}
}时间： 击败了18.88%
内存： 击败了82.02%
