面试热题（两数之和）

ゞ浴缸里的玫瑰 2023-10-14 18:13 56阅读 0赞

> 给定一个整数数组 `nums` 和一个整数目标值 `target`，请你在该数组中找出 **和为目标值** *`target`* 的那 **两个** 整数，并返回它们的数组下标。
> 
> 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
> 
> 你可以按任意顺序返回答案。
> 
>     输入：nums = [2,7,11,15], target = 9
>     输出：[0,1]
>     解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

相信两数之和是很多同学梦开始的地方，曾经的自己，看到这道题无从下手的样子是否还记得？现在你又会用多少种方式去解决它呢？ 今天我们用3种方法来解决这道极具思考的问题

*  for循环（枚举）

![3778442f8cde45229c1aec5c3b9bc546.png][]

两层for循环，枚举每一个数，看是否符合情况（这种方法时最朴素的，但也是复杂度最高的）

![50e56fcef37a4712971a94778f2b1ed7.png][]

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;
                      }
            }

你们觉得这样写正确么？

我一运行：

![84ffed4b4275435bb7e4de5a311a226f.png][]

结果居然出错了？难道是我们的思路出现的问题？NONONO,只是我们少考虑了有某种情况，这种用Map的思路类似于循环遍历，但是Map的查找是O(1)的，所以当我们枚举的这个值为target/2的时候，就会出现上面这种情况，那么我们知道枚举的数字不是当前set包含中的这个数字呢？刚刚不是说了，Map中的value是key值的索引，只要我们进行判断当前的枚举的i和map中这个key的value值是否一样就可有判断出是否是同一个数，只需要加上这么一个小小的判别条件

if(i!=map.get(target-nums[i])){
              ......
    }

然后不出意外，果然就AC了

![077a2f40a7024d139fac8a795778bca2.png][]

源代码：

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\]代表的是值的索引

![f9b6b1ed34064ddea0b05469a08e797e.png][]

首先我们先对二维数组进行排序，自定义的排序方式会出现

![bd87d94bc22d474d95c911f57cc22944.png][]

所以我们应该自定义比较器

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;
        }

![083a8ac7699b434cba3e94cc8930383f.png][]

毫无疑问过了，希望今天的博客能给大家带来一点帮助，更主要的是拓阔思路，即使是最简单的题，做完一遍过了以后，我们应该还要想想有没有其他的方式去解决，这样才能不断的进步，不断的向前，我想到了的一句话“我不怕会一万种腿法的人，我怕的是把一种腿法练一万次的人”，共勉之！！！

[3778442f8cde45229c1aec5c3b9bc546.png]: https://img-blog.csdnimg.cn/3778442f8cde45229c1aec5c3b9bc546.png
[50e56fcef37a4712971a94778f2b1ed7.png]: https://img-blog.csdnimg.cn/50e56fcef37a4712971a94778f2b1ed7.png
[84ffed4b4275435bb7e4de5a311a226f.png]: https://img-blog.csdnimg.cn/84ffed4b4275435bb7e4de5a311a226f.png
[077a2f40a7024d139fac8a795778bca2.png]: https://img-blog.csdnimg.cn/077a2f40a7024d139fac8a795778bca2.png
[f9b6b1ed34064ddea0b05469a08e797e.png]: https://img-blog.csdnimg.cn/f9b6b1ed34064ddea0b05469a08e797e.png
[bd87d94bc22d474d95c911f57cc22944.png]: https://img-blog.csdnimg.cn/bd87d94bc22d474d95c911f57cc22944.png
[083a8ac7699b434cba3e94cc8930383f.png]: https://img-blog.csdnimg.cn/083a8ac7699b434cba3e94cc8930383f.png