力扣打卡之两数之和【有序数组和无序数组】

无序数组

题目描述

给定一个数组numbers，从数组中找到两个数据满足两数之和等于目标值target

假设每个输入只对应唯一的元素，并且不可以重复使用相同的元素

解题思路

方法一：暴力求解

在无序数组中我们又有两种方式进行求解

我们可以使用双重for循环进行寻找，然后最后就可以得到我们想要的结果了

方法二：使用hashmap

我们可以使用hashmap的键值对来进行操作

我们在得到数组中的一个数据的时候我们只用知道target-nums[i]有没有在里面就可以，如果在里面就说明是包含的，不在里面可能就不行了

代码展示

方法一 暴力求解

public int[] solution(int nums[],int target)
{
    for(int i=0;i
        {
            for(int j=i+1;j
                if(nums[i]+nums[j]==target) 
                    return new int[]{i,j};
            }
        }
    return new int[0];
}
 

方法二：hashmap

public int[] solution1(int[] nums,int target){
    
    Map hashmap=new HashMap();
    for(int i=0;i
        if(hashmap.containsKey(target-nums[i]){
            return new int[]{map.get(target-nums[i]),i};
        }
        map.put(nums[i],i);  //如果当前没有找到就往后面继续去找
    }
    return new int[0];
}

总结

我们会发现使用hashmap的方式相对于暴力求解，时间复杂度缩小了很多很多；暴力求解的时间复度为O(n^2)而使用hashmap的时间复杂度为O(n)

有序数组

题目描述

给定一个升序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target；假设每个输入只对应唯一的答案， 而且不可以重复使用相同的元素。

解题思路

这里当然使用无序数组中的方法也都是可以的

方法一：二分查找

我们可以先固定一个位置上的元素，然后对后面的元素进行二分查找，找到元素如果等于target-nums[i]，就返回，如果不相等根据大小选择往后或者往前进行

方法二：双指针

我们还可以使用双指针的方式进行，前面我们在学习寻找数组的中心下标的时候也使用了这个方法

力扣打卡之寻找数组的中心下标_young_man2的博客-CSDN博客

代码展示

方法一：二分查找

public int[] twoSearch(int[] nums,int target){
    
    for(int i=0;i//我们需要从最开始往后面去找元素
        int low=i,high=nums.length-1;
        while(low<=high){
            int mid=low+(high-low)/2;
            if(nums[mid]==target-nums[i]) return new int[]{i,mid};
            else if(nums[mid]1;
            else high=mid-1;
        }
    }
    return new int[0];
 
}

方法二：双指针

public int[] twoPoint(int target,int[] nums){
    //使用双指针怎么实现？
    int low=0;
    int high=nums.length-1;
    while(low
        if(nums[low]+nums[high]==target) return new int[]{low,high};
        else if(nums[low]+nums[high]>target) high--;
        else if(nums[low]+nums[high]
    }
    return new int[0];
}

总结

这里使用双指针可以明显的发现代码要简洁很多

那么什么时候可以使用双指针进行求解？

双指针算法指的是在重复遍历对象的过程中，不是在两个循环中使用单个指针进行重复访问，而是在一个循环中使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行访问。

好看的图片分享（摄于我的大学）

最后想在文章的最后给自己一个忠告来提醒自己吧-----------人生的路很长，希望你做决定之前可以三思而后行