面试热题(两数之和)

给定一个整数数组 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;
    }

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/69727.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

STL初探

STL简介 STL(standard template libaray - 标准模板库)是C标准库的重要组成部分&#xff0c;不仅是一个可复用的组件库&#xff0c;而且是一个包罗数据结构与算法的软件框架。 STL的一些版本 原始版本 Alexander Stepanov、Meng Lee 在惠普实验室完成的原始版本&#xff0c;…

【UE4 RTS】07-Camera Boundaries

前言 本篇实现的效果是当CameraPawn移动到地图边缘时会被阻挡。 效果 步骤 1. 打开项目设置&#xff0c;在“引擎-碰撞”中&#xff0c;点击“新建Object通道” 新建通道命名为“MapBoundaries”&#xff0c;然后点击接受 2. 向视口中添加 阻挡体积 调整阻挡体积的缩放 向四…

孤立随机森林(Isolation Forest)(Python实现)

目录 1 简介 2 孤立随机森林算法 2.1 算法概述 2.2 原理介绍 2.3 算法步骤 3 参数讲解 4 Python代码实现 5 结果 1 简介 孤立森林&#xff08;isolation Forest&#xff09;是一种高效的异常检测算法&#xff0c;它和随机森林类似&#xff0c;但每次选择划分属性和划…

Zookeeper 面试题

一、ZooKeeper 基础题 1.1、Zookeeper 的典型应用场景 Zookeeper 是一个典型的发布/订阅模式的分布式数据管理与协调框架&#xff0c;开发人员可以使用它来进行分布式数据的发布和订阅。 通过对 Zookeeper 中丰富的数据节点进行交叉使用&#xff0c;配合 Watcher 事件通知机…

EFLFK——ELK日志分析系统+kafka+filebeat架构

环境准备 node1节点192.168.40.16elasticsearch2c/4Gnode2节点192.168.40.17elasticsearch2c/4GApache节点192.168.40.170logstash/Apache/kibana2c/4Gfilebeat节点192.168.40.20filebeat2c/4G https://blog.csdn.net/m0_57554344/article/details/132059066?spm1001.2014.30…

设计模式(2)工厂方法模式

一、 1、介绍&#xff1a;定义一个用于创建对象的接口&#xff0c;让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到其子类。简单工厂模式的最大优点在于工厂类中包含了必要的逻辑判断&#xff0c;根据客户端的选择条件动态实例化相关的类&#xff0c;对于客户端来说…

UML-状态图

目录 状态图 状态图的图符 状态机 状态 ​转换 电话机状态图 活动图和状态图区别&#xff1a; 状态图 状态图(Statechart Diagram)是描述一个实体基于事件反应的动态行为&#xff0c;显示了该实体如何根据当前所处的状态对不同的事件做出反应。通常我们创建一个UML状态…

中级课程——CSRF

文章目录 案例原理挖掘 案例 原理 挖掘 挖掘详情 首先就是对目标敏感部位进行抓包分析&#xff0c;比如修改信息、转账、添加信息等等。通常一个数据包HTTP请求头里边都会有一个Referer&#xff0c;这个需要特别去验证。比如放到Burpsuit Repeater里边去测试&#xff1a;去掉…

语音同声翻译软件助你跨越语言障碍

嘿&#xff0c;你在日常工作中是否曾经参加过跨国会议&#xff0c;是否也曾由于语言不通而感到尴尬&#xff1f;别担心&#xff0c;因为现在有了会议实时翻译软件&#xff0c;这些问题都将成为过去式&#xff01;那么你知道会议实时翻译的软件有哪些吗&#xff1f;接下来就让我…

无涯教程-Perl - mkdir函数

描述 此功能使用MODE指定的模式创建一个名称和路径EXPR的目录,为清楚起见,应将其作为八进制值提供。 语法 以下是此函数的简单语法- mkdir EXPR,MODE返回值 如果失败,此函数返回0,如果成功,则返回1。 例 以下是显示其基本用法的示例代码- #!/usr/bin/perl -w$dirname &…

【计算机视觉|生成对抗】条件生成对抗网络(CGAN)

本系列博文为深度学习/计算机视觉论文笔记&#xff0c;转载请注明出处 标题&#xff1a;Conditional Generative Adversarial Nets 链接&#xff1a;[1411.1784] Conditional Generative Adversarial Nets (arxiv.org) 摘要 生成对抗网络&#xff08;Generative Adversarial…

最大子数组和——力扣53

文章目录 题目描述解法一 动态规划题目描述 解法一 动态规划 int maxSubArray(vector<int>& nums){int pre=0, res=nums

自动测试框架airtest应用一:将XX读书书籍保存为PDF

一、Airtest的简介 Airtest是网易出品的一款基于图像识别和poco控件识别的一款UI自动化测试工具。Airtest的框架是网易团队自己开发的一个图像识别框架&#xff0c;这个框架的祖宗就是一种新颖的图形脚本语言Sikuli。Sikuli这个框架的原理是这样的&#xff0c;计算机用户不需要…

微软杀入Web3:打造基于区块链的AI产品

作者&#xff1a;秦晋 2023年1月&#xff0c;微软向 ChatGPT 创建者 OpenAI 投资 100 亿美元&#xff0c;在AI业界引发格外关注。此举也让微软在AI的战略探索上提前取得有利位置。 2023年3月&#xff0c;微软软件工程师 Albacore 披露微软正在为Edge 浏览器测试内置的非托管加密…

Linux 共享内存mmap,进程通信

文章目录 前言一、存储映射 I/O二、mmap&#xff0c; munmap三、父子进程间 mmap 通信四、非血缘关系进程间 mmap 提通信五、mmap 匿名映射区总结 前言 进程间通信是操作系统中重要的概念之一&#xff0c;使得不同的进程可以相互交换数据和进行协作。其中&#xff0c;共享内存…

安达发|企业如何提高生产实现精细化管理

随着市场竞争的加剧&#xff0c;企业如何提高生产效率和降低成本成为了关键。本文将探讨生产计划排程表的制定方法&#xff0c;帮助企业实现精细化管理&#xff0c;提升竞争力。 在传统的生产管理中&#xff0c;企业往往依赖于人工经验和直觉来制定生产计划&#xff0c;导致生产…

刷题笔记 day9

1658 将 x 减到 0 的最小操作数 解析&#xff1a;1. 当数组的两端的数都大于x时&#xff0c;直接返回 -1。 2. 当数组所有数之和小于 x 时 &#xff0c;直接返回 -1。 3. 数组中可以将 x 消除为0&#xff0c;那么可以从左边减小为 0 &#xff1b;可以从右边减小为 0 &#xff1…

深眸科技|发现AI+3D视觉的价值,技术升级加速视觉应用产品国产替代

随着中国工业化进程的不断深入和智能制造浪潮的影响&#xff0c;工业生产对于机器视觉技术的需求不断攀升&#xff0c;其应用范围覆盖了工业领域的众多行业&#xff0c;包括3C电子、汽车、半导体、新能源、物流等。 据GGII发布的最新数据显示&#xff0c;近年来我国机器视觉市…

数据结构篇七:排序

文章目录 前言1.插入排序1.1 基本思想1.2 代码实现1.3 特性总结 2.希尔排序2.1 基本思想2.2 代码实现2.3 特性总结 3. 选择排序3.1 基本思想3.2 代码实现3.3 特性总结 4. 堆排序4.1 基本思想4.2 代码实现4.3 特性总结 5. 冒泡排序5.1 基本思想5.2 代码实现5.3 特性总结 6. 快速…

机器学习笔记之优化算法(十三)关于二次上界引理

机器学习笔记之优化算法——关于二次上界引理 引言回顾&#xff1a;利普希兹连续梯度下降法介绍 二次上界引理&#xff1a;介绍与作用二次上界与最优步长之间的关系二次上界引理证明过程 引言 本节将介绍二次上界的具体作用以及它的证明过程。 回顾&#xff1a; 利普希兹连续…