每周leetcode - leetcode704/34/88/1

• • • • leetcode-704 二分查找
      • leetcode-34 在排序数组中查找元素的第一个和最后一个位置
      • leetcode-88 合并两个有序数组
      • leetcode-1 两数之和

方法1 ：

public class Solution {
    public int search1(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        while (start<=end){
            int mid = start + (end-start)/2;
            // 先判断有没有找到
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                end= mid-1;
            }else{
                start = mid+1;
            }
        }
        //如果最后没找到，start和end会指向同一个值，如果找到最后才找到，start和end和mid会指向target
        return -1;
    }
}

方法2 ：

public int search(int[] nums, int target) {
    int start = 0;
    int end = nums.length-1;
    while (start+1=nums[mid]){
            start= mid;
        }else{
            end= mid;
        }
    }
    //循环结束后，start和end会指向两个值，永远不会指向同一个
    if(nums[start]==target) return start;
    if(nums[end]==target) return end;
    return -1;
}

public class Solution {
    public  int[] searchRange(int[] nums, int target) {
        if(nums==null || nums.length==0) return new int[]{-1,-1};
        List result = new ArrayList<>();
        int first = findFirst( nums, target);
        int last = findLast( nums, target);
        return new int[]{first,last};
    }

    private int findLast(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        while (start+1 
leetcode-88 合并两个有序数组 
class Solution {
    public  void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1;
        int j = n-1;
        int k = m+n-1;
        while (i>=0 && j>=0){
            if(nums1[i]>=nums2[j]){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
        while (j>=0){
            nums1[k--] = nums2[j--];
        }
        while (i>=0){
            nums1[k--] = nums1[i--];
        }
    }
}
 
leetcode-1 两数之和 
方法1：暴力法，时间复杂度O(n^2)
 
class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums.length==0 || nums==null) return null;
        for(int i=0;i 
方法2：用空间换时间，时间复杂度O(n)。空间复杂度O(n)
 
class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums.length==0 || nums==null) return null;
        Map map = new HashMap<>();
        for(int i=0;i