力扣经典题目解析--两数之和

两数之和

题目地址: 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

 简单来说就是在一个数组中找出两个数,这两个数相加要等于给定的target,下面是完整的题目:

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

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

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

示例 1:

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

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

暴力法

看到这个题目最简单的想法就是双重遍历,把值相加,然后返回对应的下标

public int[] twoSum1(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < nums.length; j++) {
            //双重遍历,如果相加等于target则返回下标
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    throw new IllegalArgumentException("no solution");
}

 打开力扣网址,选择java,把代码贴进去,点运行

 看右下角,发现执行测试用例时报错了

 因为同一个元素不能重复出现,所以需要优化下

public int[] twoSum1(int[] nums, int target) {
    // 第一层循环到倒数第二个
    for (int i = 0; i < nums.length - 1; i++) {
        // 第二层循环从i + 1开始
        for (int j = i + 1; j < nums.length; j++) {
            //双重遍历,如果相加等于target则返回下标
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    throw new IllegalArgumentException("no solution");
}

效果:

两次遍历哈希表 

使用哈希表记录值与索引的对应关系,通过target-val1得到val2,通过哈希表找val2的索引

public int[] twoSum2(int[] nums, int target) {
    int n = nums.length;
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < n; i++) {
        int thatNum = target - nums[i];
        Integer index = map.get(thatNum);
        if (index != null && !index.equals(i)) {
            return new int[]{i, index};
        }
    }
    throw new IllegalArgumentException("no solution");
}

效果:

一次遍历哈希表

 在上面一个算法中,我们遍历了两次数组,第一次插入哈希表,第二次找差值,其实可以只遍历一次,找到就返回,没找到再插入哈希表继续找,比如[1,2]这个数组的target是3,找第一个的时候差值是2,去哈希表没找到,就把1放入哈希表,遍历到2的时候差值是1,在哈希表就能找到了

public int[] twoSum3(int[] nums, int target) {
    int n = nums.length;
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
        int thatNum = target - nums[i];
        Integer index = map.get(thatNum);
        if (index != null && !index.equals(i)) {
            return new int[]{i, index};
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("no solution");
}

效果:

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

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

相关文章

阿里云SSL免费证书到期自动申请部署程序

阿里云的免费证书只有3个月的有效期&#xff0c;不注意就过期了&#xff0c;还要手动申请然后部署&#xff0c;很是麻烦&#xff0c;于是写了这个小工具。上班期间抽空写的&#xff0c;没有仔细测试&#xff0c;可能存在一些问题&#xff0c;大家可以自己clone代码改改&#xf…

(done) 矩阵的对角化,以及是否可对角化的判断、还有对角化的本质。相似对角化计算过程

相似对角化 和 对角化 很大程度上是一回事 甚至判断两个矩阵的相似性&#xff0c;也跟对角化有很大关系 参考视频1&#xff1a;https://www.bilibili.com/video/BV1PA411T7b5/?spm_id_from333.788&vd_source7a1a0bc74158c6993c7355c5490fc600 参考视频2&#xff1a;http…

【移动安全】MobSF联动安卓模拟器配置动态分析教程

原文链接 MobSF联动安卓模拟器配置动态分析教程 实现方式 Windows开启安卓模拟器并进行相关配置作为调试客户端&#xff0c;Linux使用docker开启MobSF作为服务端。 好处&#xff1a;干净&#xff0c;部署简单&#xff0c;不用安装乱七八糟的环境&#xff0c;防止破坏其他应…

最新YOLOv9论文理论:使用可编程梯度信息学习您想学习的内容 | Programmable Gradient Information

YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information YOLOv9 论文地址&#xff1a;https://arxiv.org/pdf/2402.13616.pdf 摘要 当今的深度学习方法侧重于如何设计最合适的目标函数&#xff0c;以便模型的预测结果最接近真实情况。同时&…

CSS轻松学:简单易懂的CSS基础指南

css基础 更多web开发知识欢迎访问我的专栏>>> 01-CSS初体验 层叠样式表 (Cascading Style Sheets&#xff0c;缩写为 CSS&#xff09;&#xff0c;是一种 样式表 语言&#xff0c;用来描述 HTML 文档的呈现&#xff08;美化内容&#xff09;。 书写位置&#xff1a;…

Qt事件过滤器

1. 事件过滤器 void QObject::installEventFilter(QObject *filterObj) bool eventFilter(QObject *obj, QEvent *event); filterObj表示事件筛选器对象&#xff0c;它接收发送到此QObject对象&#xff08;安装事件过滤器的部件对象&#xff09;的所有事件。筛选器可以停止事件…

【Oracle】玩转Oracle数据库(四):SQL语言

前言 嘿&#xff0c;各位数据达人们&#xff01;准备好迎接新的挑战了吗&#xff1f;今天&#xff0c;我们要探索的是数据库世界的魔法咒语——SQL语言&#xff01;&#x1f52e;&#x1f4bb; 在这篇博文【Oracle】玩转Oracle数据库&#xff08;四&#xff09;&#xff1a;SQL…

ssm+springmvc基于springboot的宠物领养系统的设计与实现_j5fk4

宠物领养系统主要是为了提高管理员的工作效率&#xff0c;满足管理员对更方便、更快、更好地存储所有信息和数据检索功能的要求。通过对多个类似网站的合理分析&#xff0c;确定了宠物领养系统的各个模块。考虑到用户的可操作性&#xff0c;经过深入调查研究&#xff0c;遵循系…

Web 前端 UI 框架Bootstrap简介与基本使用

Bootstrap 是一个流行的前端 UI 框架&#xff0c;用于快速开发响应式和移动设备优先的网页。它由 Twitter 的设计师和工程师开发&#xff0c;现在由一群志愿者维护。Bootstrap 提供了一套丰富的 HTML、CSS 和 JavaScript 组件&#xff0c;可以帮助开发者轻松地构建和定制网页和…

css3d制作正方体

使用css3d技术 &#xff0c;制作一个可以动态动画的正方体模型 效果图&#xff1a; 代码如下&#xff1a; <!DOCTYPE html> <html> <head><style>/* 设置高度宽度100%并且左右居中、上下居中 */html,body {width: 100%;height: 100%;display: flex…

【Python笔记-设计模式】对象池模式

一、说明 用于管理对象的生命周期&#xff0c;重用已经创建的对象&#xff0c;从而减少资源消耗和创建对象的开销 (一) 解决问题 主要解决频繁创建和销毁对象所带来的性能开销问题。如数据库连接、线程管理、网络连接等&#xff0c;对象的创建和销毁成本相对较高&#xff0c…

求最短路问题总结

图论题最重要的是如何抽象出图&#xff0c;怎么定义点和边。 朴素Dijkstra算法&#xff1a;稠密图 堆优化版的Dijkstra算法&#xff1a;稀疏图 存在负权边一般用SPFA&#xff0c;个别情况用Bellman-Fold。 多源汇最短路用Floyd算法。

React18源码: reconciler执行流程

reconciler执行流程 1 &#xff09;概述 此处先归纳一下react-reconciler包的主要作用&#xff0c;将主要功能分为4个方面&#xff1a; 输入&#xff1a;暴露api函数&#xff08;如&#xff1a;scheduleUpdateOnFiber&#xff09;, 供给其他包&#xff08;如react包&#xff0…

mysql mgr集群部署

一、前言 mysql mgr集群是为了实现mysql高可用&#xff0c;分为单主集群和多主集群&#xff0c;单主集群只有一个主节点可写&#xff0c;节点发生故障时&#xff0c;自动进行主从的故障切换&#xff0c;多主集群所有节点都可写&#xff0c;当节点发生故障时&#xff0c;将故障节…

activeMq将mqtt发布订阅转成消息队列

1、activemq.xml置文件新增如下内容 2、mqttx测试发送&#xff1a; 主题&#xff08;配置的模糊匹配&#xff0c;为了并发&#xff09;&#xff1a;VirtualTopic/device/sendData/12312 3、mqtt接收的结果 4、程序处理 package comimport cn.hutool.core.date.DateUtil; imp…

python专业版破解激活(超详细)

python专业版破解激活 1.下载pycharm应用程序 这里我使用的版本是pycharm-professional-2023.3.2 下载pycharm程序的连接为&#xff1a; 百度网盘 请输入提取码 提取码为&#xff1a;nym0 2.安装 选择安装路径 下一步 这里全选 下一步 这里直接点击安装就可&#xff0c;其…

探索分布式强一致性奥秘:Paxos共识算法的精妙之旅

提到分布式算法&#xff0c;就不得不提 Paxos 算法&#xff0c;在过去几十年里&#xff0c;它基本上是分布式共识的代名词&#xff0c;因为当前一批常用的共识算法都是基于它改进的。比如&#xff0c;Fast Paxos 算法、Cheap Paxos、Raft 算法等。 由莱斯利兰伯特&#xff08;L…

R语言数据分析(五)

R语言数据分析&#xff08;五&#xff09; 文章目录 R语言数据分析&#xff08;五&#xff09;前言一、什么是整洁的数据二、延长数据2.1 列名中的数据值2.2 pivot_longer()的处理原理2.3 列名中包含许多变量的情况2.4 列名同时包含数据和变量 三、扩宽数据3.1 pivot_wider的处…

Electron实战之环境搭建

工欲善其事必先利其器&#xff0c;在进行实战开发的时候&#xff0c;我们最终的步骤是搞好一个舒服的开发环境&#xff0c;目前支持 Vue 的 Electron 工程化工具主要有 electron-vue、Vue CLI Plugin Electron Builder、electron-vite。 接下来我们将分别介绍基于 Vue CLI Plu…

查询数据库的编码集Oracle,MySQL

1、查询数据库的编码集Oracle,MySQL 1.1、oracle select * from v$nls_parameters where parameterNLS_CHARACTERSET; 查询版本&#xff1a;SELECT * FROM v$version 2、MySQL编码集 SELECT DEFAULT_CHARACTER_SET_NAME, DEFAULT_COLLATION_NAME FROM information_schema.SC…