数组

1.数组三元组

给一个n元数组s，找出是否有a+b+c=0的三元组，三元组不能重复，并且降序排列

  import java.util.*;
  public class Solution {
      public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
            //存放最终答案的二维数组
          ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
          int len = num.length;
           //特判：长度<3的数组不满足条件
          if(len<3){
              return ans;
          }
          //排序O(nlogn)
          Arrays.sort(num);
          for(int i=0;i<len;i++){
            //如果nums[i]已经大于0，就没必要继续往后了，因为和就是0啊
              if(num[i]>0){
                  return ans;
              }
              //注意考虑越界i>0,主要功能是排除重复值
              if(i>0 && num[i]==num[i-1]){
                  continue;
              }
              //声明指针
              int cur = num[i];
              int left = i+1;
                //从尾部开始
              int right =len-1;
              while(left<right){
                //满足条件的三数和
                  int tp_ans = cur+num[left]+num[right];
                //如果已经找到和为0
                 if(tp_ans==0){
                    //创建一个数组，并将满足条件的三元素放进去
                     ArrayList<Integer> list = new ArrayList<>();
                     list.add(cur);
                     list.add(num[left]);
                     list.add(num[right]);
                    //将最终的结果存入答案数组ans中
                     ans.add(list);
                     //判断是left指针指向是否重复
                    while(left<right && num[left]==num[left+1]){
                        left++;
                    }
                    //判断是right指针指向是否重复
                     while(left<right && num[right]==num[right-1]){
                         right--;
                     }
                    //移动指针
                     left++;
                     right--;
                 }else if(tp_ans<0){
                     left++;
                 }else{
                     right--;
                 } 
              }
          }
          return ans;
      }
  }

2.求数组中最长连续子序列

public int MLS(int[] arr) {
    if (arr == null || arr.length == 0)
        return 0;
    int longest = 1;//记录最长的有序序列
    int count = 1;//目前有序序列的长度
    //先对数组进行排序
    Arrays.sort(arr);
    for (int i = 1; i < arr.length; i++) {
        //跳过重复的
        if (arr[i] == arr[i - 1])
            continue;
        //比前一个大1，可以构成连续的序列，count++
        if ((arr[i] - arr[i - 1]) == 1) {
            count++;
        } else {
            //没有比前一个大1，不可能构成连续的，
            //count重置为1
            count = 1;
        }
        //记录最长的序列长度
        longest = Math.max(longest, count);
    }
    return longest;
}

3.求数组中最长递增子序列

如果有多个长度相等的答案，取最小的一个

//set中last()返回最大，ceiling(k)返回大于等于k的最小元素，headSet(K)返回小于等于K的的set
public int[] LIS (int[] temp) {
        int N = temp.length;
        int[] dp = new int[N];
        Arrays.fill(dp, 1);
        TreeSet<Integer> set = new TreeSet<>();
        set.add(temp[0]);
        for(int i = 1; i < dp.length; i++) {
            if(temp[i] > set.last()) {
                set.add(temp[i]);
                dp[i] = set.size();
            } else {
                int first = set.ceiling(temp[i]);
                set.remove(first);
                set.add(temp[i]);
                dp[i] = set.headSet(temp[i]).size() + 1;
            }
        }
        int[] res = new int[set.size()];
        for(int i = temp.length - 1, j = set.size(); i >= 0; i--) {
            if(dp[i] == j) {
                res[--j] = temp[i];
            }
        }
        return res;
    }

4.合并区间

合并重叠数组，如输入[[10,30],[20,60],[80,100],[150,180]]，输出：[[10,60],[80,100],[150,180]]

import java.util.*;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval o1, Interval o2) {
                return o1.start-o2.start;
            }
        });
        for (int i = 1; i < intervals.size(); i++) {
            int preStart = intervals.get(i - 1).start;
            int preEnd = intervals.get(i - 1).end;
            int curStart = intervals.get(i).start;
            int curEnd = intervals.get(i).end;
            if (curStart <= preEnd) {
                intervals.set(i, new Interval(preStart, Math.max(preEnd, curEnd)));
                intervals.set(i - 1, null);
            }
        }
        while (intervals.remove(null)) ;
        return intervals;
    }
}