算法2题

1 Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
给定整型数组，从中找到两个数，使得两数之和等于目标值，并输出两数的下标（从0开始）。
可以假设每个输出只有一个对应的结果，不会重复使用同一个元素

 /**
     * 方法2：
     * 借助于map存储数值和数组下标
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * @param numbers
     * @param target
     * @return
     */
 public static int[] twoNumbers(int[] numbers, int target){
        int[] result = new int[2];
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < numbers.length; i++){
            //要找的数值
            int temp = target - numbers[i];
            //找到了key
            if(map.containsKey(temp)){
                result[0] = map.get(temp);
                result[1] = i;
                return result;
            }else {
                //key = 数值，value = 下标
                map.put(numbers[i],i);
            }
        }
        return result;
    }

2 Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.
给定一组区间，合并所有重叠区间

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 给定一组区间，合并所有重叠区间
 */
public class Demo2 {

    /**
     * 区间类
     */
    static class Interval{
        //区间起点
        private int start;
        //区间终点
        private int end;
        public Interval() {
        }

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "[" + start + ", " + end + ']';
        }
    }

    //区间类比较器,比较start
    static class IntervalComparator implements Comparator<Interval>{
        @Override
        public int compare(Interval o1, Interval o2) {
            return o1.start - o2.start;
        }
    }

    /**
     * 合并区间
     * @param intervals
     * @return
     */
    public static List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<>();
        if(intervals == null || intervals.size() == 0)
            return result;
        //使用比较器，按照Interval的start排序
        intervals.sort(new IntervalComparator());
        System.out.println("排序后："+intervals);
        //数组第一个区间
        Interval prev = intervals.get(0);
        for(int i = 1;i < intervals.size(); i++){
            //逐个比较前一个的end是否比当前的end大，来判断2个区间是否有重叠
            Interval curr = intervals.get(i);
            if(prev.end >= curr.start){
                //有重叠，新建一个Interval实例，新的start是前一个的start，新的end的值是两个的end的最大值
                prev = new Interval(prev.start,Math.max(prev.end,curr.end));
            }else{
                //不重叠，就将前一个添加到result中
                result.add(prev);
                prev = curr;
            }
        }
        //循环结束后，把最后一个prev添加到result中
        result.add(prev);
        return result;
    }

    //Input: [[1,3],[2,6],[8,10],[15,18]]
    //Output: [[1,6],[8,10],[15,18]]
    public static void main(String[] args) {
        List<Interval> intervals = new ArrayList<>();
        intervals.add(new Interval(1,3));
        intervals.add(new Interval(8,10));
        intervals.add(new Interval(2,6));
        intervals.add(new Interval(15,18));
        System.out.println("排序前：" + intervals);
        List<Interval> list = merge(intervals);
        System.out.println("合并后：" + list);
    }

}