给定一个整数数组
nums
和一个整数目标值target
,请你在该数组中找出 和为目标值target
的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
相信两数之和是很多同学梦开始的地方,曾经的自己,看到这道题无从下手的样子是否还记得?现在你又会用多少种方式去解决它呢? 今天我们用3种方法来解决这道极具思考的问题
- for循环(枚举)
两层for循环,枚举每一个数,看是否符合情况(这种方法时最朴素的,但也是复杂度最高的)
public int[] twoSum(int[] nums, int target) {
//维护长度为2的数组,将最后的结果添加到数组中
int [] arr=new int[2];
//枚举第一个数
for(int i=0;i<nums.length;i++){
//枚举第二个数
for(int j=i+1;j<nums.length;j++){
//如果相等就说明找到结果
if(nums[i]+nums[j]==target){
arr[0]=i;
arr[1]=j;
}
}
}
return arr;
}
- 哈希表
怎么利用哈希表解决这道题呢?
我们可以利用Map进行对原数组中的元素进行value和索引的联系,key绑定数组中的元素,value绑定对应的索引,这样我们枚举数组中的每个元素,然后载判断target-num[i]的这个元素是否在Map中存在,存在的话就说明有满足条件的值
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
//判断Map中是否存在target-nums[i]
if(map.containsKey(target-nums[i])){
res[0]=i;
res[1]=map.get(target-nums[i]);
return res;
}
}
你们觉得这样写正确么?
我一运行:
结果居然出错了?难道是我们的思路出现的问题?NONONO,只是我们少考虑了有某种情况,这种用Map的思路类似于循环遍历,但是Map的查找是O(1)的,所以当我们枚举的这个值为target/2的时候,就会出现上面这种情况,那么我们知道枚举的数字不是当前set包含中的这个数字呢?刚刚不是说了,Map中的value是key值的索引,只要我们进行判断当前的枚举的i和map中这个key的value值是否一样就可有判断出是否是同一个数,只需要加上这么一个小小的判别条件
if(i!=map.get(target-nums[i])){
......
}
然后不出意外,果然就AC了
源代码:
public int[] twoSum(int[] nums, int target) {
int[] res=new int[2];
if(nums==null||nums.length==0){
return res;
}
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){
if(i!=map.get(target-nums[i])){
res[0]=i;
res[1]=map.get(target-nums[i]);
return res;
}
}
}
return res;
}
- 排序+双指针
排序双指针,这种容易想,但是不太好实现,因为想用双指针从两端往中间收缩的情况,前提是数组必须是有序的,但是题目中给我们的是无序数组,如果是要我们返回值的话,直接排序,利用双指针就可以找到结果,但是这个题偏偏让你返回的结果值的索引,这就有点头大了,如果直接排序,对应值的索引的就会发生改变,如果不排序,就无法使用双指针(其实无序也可以用,只是解决的方法不一样)
有人肯定又会说?啊!!!这个数组我们可以用Hash表的方式,去将它们的值和索引一一对应起来不就可以了么?能想到这里说明你对这个问题算是熟悉了,但还是没有完全吃透,怎么说,如果,数组中有两个值一样的元素,后面添加的元素的key值肯定会把前面添加的key值进行覆盖,那么我们第一次添加的元素那不成立无效元素了么?所以利用这种方式显然是行不同的,那这道题难道就没有一个合适的解决办法了么?
我们现在要的是key和index进行关联,且相同的元素还不能进行覆盖,维护两个变量,而且还有对应关系,这是不是和我们坐标轴的(x,y)差不多,所以我们可以利用二维数组[x][y]去解决这个问题,[x][0]代表的是值,[x][1]代表的是值的索引
首先我们先对二维数组进行排序,自定义的排序方式会出现
所以我们应该自定义比较器
Arrays.sort(resNum,(o1,o2)->{
//数组中第一个相等? 按照第二个大小进行排序(升序):按照第二个大小进行排序(升序)
return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0];
});
然后就是双指针的固定模板了(必会)
//左指针
int left=0;
//右指针
int right=n-1;
while(left<right){
int sum=nums[left]+nums[right];
//如果相等找到结果
if(sum==target){
reutrn ...;
//如果大于,说明,右边的太大了,要往左进行收缩
}else if(sum>target){
right--;
//如果小于,说明左边太小了,要往右进行收缩
}else{
left++;
}
}
源码如下:
public int[] twoSum(int[] nums, int target) {
int[] res=new int[2];
//对入参进行判断
if(nums==null||nums.length==0){
return res;
}
//声明一个二维数组
int[][] resNum=new int[nums.length][2];
//将原数组中的值和index进行映射(关联)
for(int i=0;i<nums.length;i++){
resNum[i][0]=nums[i];
resNum[i][1]=i;
}
//自定义比较器
Arrays.sort(resNum,(o1,o2)->{
return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0];
});
//反向双指针的模板变写
int left=0;
int right=nums.length-1;
while(left<right){
int sum=resNum[left][0]+resNum[right][0];
//碰到满足题意的值直接进行返回
if(sum==target){
res[0]=resNum[left][1];
res[1]=resNum[right][1];
return res;
}else if(sum>target){
right--;
}else{
left++;
}
}
return res;
}
文章来源:https://www.toymoban.com/news/detail-642160.html
毫无疑问过了,希望今天的博客能给大家带来一点帮助,更主要的是拓阔思路,即使是最简单的题,做完一遍过了以后,我们应该还要想想有没有其他的方式去解决,这样才能不断的进步,不断的向前,我想到了的一句话“我不怕会一万种腿法的人,我怕的是把一种腿法练一万次的人”,共勉之!!! 文章来源地址https://www.toymoban.com/news/detail-642160.html
到了这里,关于面试热题(两数之和)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!