面试热题(两数之和)

这篇具有很好参考价值的文章主要介绍了面试热题(两数之和)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

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

  • for循环(枚举)

面试热题(两数之和),热题Hot100,算法,数据结构,java,面试

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

面试热题(两数之和),热题Hot100,算法,数据结构,java,面试

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

 你们觉得这样写正确么?

我一运行:

面试热题(两数之和),热题Hot100,算法,数据结构,java,面试

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

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

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

面试热题(两数之和),热题Hot100,算法,数据结构,java,面试

 源代码:

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

面试热题(两数之和),热题Hot100,算法,数据结构,java,面试

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

面试热题(两数之和),热题Hot100,算法,数据结构,java,面试

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

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

面试热题(两数之和),热题Hot100,算法,数据结构,java,面试

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

到了这里,关于面试热题(两数之和)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法Hot100系列】两数相加

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月04日
    浏览(42)
  • 【算法Hot100系列】三数之和

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月04日
    浏览(43)
  • 两数相加 LeetCode热题100

    给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。 建立链表l3,同时遍历两个链表

    2024年02月14日
    浏览(38)
  • LeetCode 热题 HOT 100

    重点是当有一个链表为空了不单独处理,按节点为0处理。 滑动窗口! 首先要判断slow需不需要更新,怎么判断?slow = max(umap[s[fast]], slow);什么意思,就是说:**umap[s[fast]]的意义是,为了在slow和fast之间不出现重复字符,slow能处于的最左位置。**如图,当j第一次到d,将umap[s[j

    2024年02月07日
    浏览(47)
  • 面试算法100:三角形中最小路径之和

    在一个由数字组成的三角形中,第1行有1个数字,第2行有2个数字,以此类推,第n行有n个数字。例如,下图是一个包含4行数字的三角形。如果每步只能前往下一行中相邻的数字,请计算从三角形顶部到底部的路径经过的数字之和的最小值。从三角形顶部到底部的路径数字之和

    2024年01月16日
    浏览(44)
  • 《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数

    本期给大家带来的是是《 LeetCode 热题 HOT 100 》第四题—— 寻找两个正序数组的中位数的 题目讲解 !!!() 本文目录 💥题意分析 💥解题思路: 1、直接法  (❌) 2、归并思想 (❌) ①《LeetCode》第88题——合并两个有序数组 3、二分查找(✔️) 整体思想: 题目如下

    2023年04月27日
    浏览(43)
  • 面试热题(三数之和)

    给你一个整数数组  nums  ,判断是否存在三元组  [nums[i], nums[j], nums[k]]  满足  i != j 、 i != k  且  j != k  ,同时还满足  nums[i] + nums[j] + nums[k] == 0  。请 你返回所有和为  0  且不重复的三元组。 注意: 答案中不可以包含重复的三元组。        梦开始的地方(两数之和)

    2024年02月12日
    浏览(29)
  • 【面试经典150 | 双指针】两数之和

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月09日
    浏览(36)
  • LeetCode热题HOT100:76. 最小覆盖子串,84.柱状图中最大的矩形、96. 不同的二叉搜索树

    题目 :给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保

    2023年04月19日
    浏览(69)
  • 【优选算法专栏】专题九:链表--------两数之和

    本专栏内容为:算法学习专栏,分为优选算法专栏,贪心算法专栏,动态规划专栏以及递归,搜索与回溯算法专栏四部分。 通过本专栏的深入学习,你可以了解并掌握算法。 💓博主csdn个人主页:小小unicorn ⏩专栏分类:算法从入门到精通 🚚代码仓库:小小unicorn的代码仓库

    2024年02月21日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包