Day_1复习

## 盛最多水的容器

class Solution {
    public int maxArea(int[] height) {
        int n = height.length , ans = 0;
        int i =  0 , j = n - 1;
        while(i < j){
            ans = Math.max(ans ,(j - i) *  Math.min(height[i],height[j]));
            if(height[i] < height[j]){
                i++;
            }else{
                j--;
            }
        }
        return ans;
    }
}

无重复字符的最长字串

class Solution {
    public int lengthOfLongestSubstring(String s) {

        Map<Character ,  Integer> map = new HashMap<>();
        int ans = 0;
        for(int start = 0 , end = 0 ; end < s.length() ; end++){

            char right = s.charAt(end);
            map.put(right, map.getOrDefault(right , 0) + 1);
            while(map.get(right) > 1){

                char left = s.charAt(start);
                map.put(left , map.get(left) - 1);
                start++;
            }
            ans = Math.max(ans, end - start + 1);


        }
        return ans;




    }
}

三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        List<List<Integer>> ans = new ArrayList<>();

        for(int i = 0 ; i < n ; i ++){
            if(i > 0 &&nums[i] == nums[i - 1] ) continue;
            int j = i + 1 , k = n - 1;
            while(j < k){
                while(j > i + 1 && j < n && nums[j] == nums[j - 1])j++;
                if(j >= k) break;
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    j++;
                }else if(sum > 0){
                    k--;
                }else if(sum < 0){
                    j++;
                }


            }

        }
        return ans;



    }
}

四数之和

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        for(int i = 0 ; i < n ; i ++){

            //去重第一个数
            if(i > 0 && nums[i] == nums[i - 1]) continue;

            for(int j = i + 1; j < n ;j++){
                //去重第二个数
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;

                //赋值第三个，第四个数
                int k = j + 1 ,p = n - 1;
                while(k < p){

                    //去重第三个数
                    while(k > j + 1 && k < n && nums[k] == nums[k - 1]) k++;

                    //如果k跳过相同元素之和的位置超过了p，本次循环结束
                    if(k >= p) break;

                    long sum = 0L + nums[i] + nums[j] + nums[k] + nums[p];

                    if(sum == target){
                        ans.add(Arrays.asList(nums[i],nums[j],nums[k],nums[p]));
                        k++;
                    }else if(sum > target){
                        p--;
                    }else if(sum < target){
                        k++;
                    }
                }

              
            }
        }
        return ans;
        
    }
}

删除链表的倒数第N个结点

/**
 * 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 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur = new ListNode(0);
        cur.next = head;


        ListNode slow = cur;
        ListNode fast = cur;

        for(int i = 0 ; i <= n ;i++){
            fast = fast.next;
        }


        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return cur.next;



    }
}

## 新学

最接近的三数之和

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        int n = nums.length;
        for(int i = 0 ; i < n ; i ++){
            if(i > 0 && nums[i] == nums[ i - 1]) continue;

            int j = i + 1 , k = n - 1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(Math.abs(sum - target) < Math.abs(ans - target)) ans = sum;
                if(ans == target){
                    return target;
                }else if(sum > target){
                    k--;
                }else if(sum < target){
                    j++;
                }

            }
        } 
        return ans;
        




    }
}