0205算法:最长连续序列、三数之和、排序链表

力扣128：最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution {
    public int longestConsecutive(int[] nums) {
        //整体思路：
        //将所有的元素都添加到hashset中
        //找到最小的起点，才开始进行判断他有多长
        //判断最长的方法：找到当前值，然后+1 判断在Set中是否存在，并更新最大长度

        //解题步骤：
        //将元素添加到Set中：
        Set<Integer> demo = new HashSet<Integer>();
        for(int num:nums){
            demo.add(num);
        }
        int maxlong = 0;
        //遍历找到最小起始节点：
        for(int num:demo){
            if(!demo.contains(num-1)){
                int currentNum = num;
                int currentLong = 1;

                //找出每个初始节点的最长路径
                while (demo.contains(currentNum+1)){
                    currentNum +=1;
                    currentLong+=1;
                }
                //更新最大长度
                maxlong = Math.max(currentLong,maxlong);
            }
        }
        return maxlong;
    }
}

力扣15：三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //存放结果
        List<List<Integer>> demo = new ArrayList<>();
        Arrays.sort(nums);
        //更新i，缩短距离
        for(int i=0;i<nums.length-2;i++){
            //去重,【只用出现的第一个不同的】
            int x= nums[i];
            if(i>0&&x==nums[i-1]) continue;//去重，【只用出现的第一个不同的】
            int j = i+1;
            int k = nums.length-1;
            //进行循环两个jk
            while(j<k){
                int s = x+nums[j] + nums[k];
                if(s>0){
                    k--;
                }else if(s<0){
                    j++;
                }else{
                    //添加到结果集
                    demo.add(List.of(x,nums[j],nums[k]));
                    //去重，【只用出现的第一个不同的】
                    for(j++;j<k && nums[j]==nums[j-1];j++);
                    for(k--;k>j && nums[k]==nums[k+1];k--);
                }
            }
        }
        return demo;
    }
}

力扣148：排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    //该方法的作用：将head为始的链表对半拆分，然后分别递归进行排序，然后将两个排好序的链表组装并排序。
    public ListNode sortList(ListNode head) {
        //时间复杂度为logn，可以使用归并排序
        //由于是链表，所以需要在每个方法的内部进行拆分
        
        //结束条件
        if(head ==null || head.next==null){
            return head;
        }
        
        ListNode fast = head.next;
        ListNode slow = head;

        //对半分
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next=null;

        //递归获得排好序的子链表
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);

        //将两个链表进行排序
        ListNode h = new ListNode(0);
        ListNode res = h;
        while(left!=null && right!=null){
            if(left.val<right.val){
                h.next = left;
                h=h.next;
                left=left.next;
            }else{
                h.next = right;
                h=h.next;
                right = right.next;
            }
        }
        //将剩余的结果链接起来
        h.next = left!=null?left:right;
        return res.next;

    }
}