02-CodeTop：12~912~53~21~1

15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if(nums==null || nums.length==0){
            return list;
        }
        Arrays.sort(nums);
        // 固定一个指针 i 
        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            // 更新指针 left和 right：[-1,0,1,2,-1,-4]
            while (left<right){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum==0){
                    list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while (left<right && nums[left]==nums[left+1]){
                        left++;
                    }
                    while (left<right && nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }else if(sum>0){
                    right--;
                }else if(sum<0){
                    left++;
                }
            }
        }
        return list;
    }
}

912. 排序数组

class Solution {
    public int[] sortArray(int[] nums) {
        if(nums==null || nums.length==0){
            return new int[0];
        }
        int left = 0;
        int right = nums.length-1;
        quickSort(nums,left,right);
        return nums;
    }
    private void quickSort(int[] nums, int left, int right) {
        if(left>right){
            return;
        }
        int index = getIndex(nums,left,right);
        quickSort(nums,left,index-1);
        quickSort(nums,index+1,right);
    }
    private int getIndex(int[] nums, int left, int right) {
        int temp = nums[left];
        while (left<right){
            while (left<right && nums[right]>=temp){
                right--;
            }
            nums[left]=nums[right];
            while (left<right && nums[left]<=temp){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = temp;
        return left;
    }
}

53. 最大子数组和

参考题解：https://leetcode.cn/problems/maximum-subarray/solution/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums==null || nums.length==0){
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for(int i=1;i<nums.length;i++){
            // 如果dp[i-1]>0，那么加上后以dp[i] 结尾的连续子数组之和会变大，否则会变小舍弃
            if(dp[i-1]>0){
                dp[i] = dp[i-1]+nums[i];
            }else {
                dp[i] = nums[i];
            }
            max = Math.max(dp[i],max);
        }
        return max;
    }
}

21. 合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (list1!=null && list2!=null){
            if(list1.val<=list2.val){
                cur.next = list1;
                list1 = list1.next;
                cur = cur.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }
        if(list1!=null){
            cur.next = list1;
        }
        if(list2!=null){
            cur.next = list2;
        }
        return dummy.next;
    }
}

1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums==null || nums.length==0){
            return new int[]{-1,-1};
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[]{-1,-1};
    }
}