leetcode_001_两数之和解析

两数之和解析

题目:

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

这个问题要求你设计一个高效的算法来找到数组中两个数,使得它们的和等于一个给定的目标值。
这要求你能够分析问题的本质,并设计出合适的解决方案。
这个问题的本质是搜索与匹配的问题,更具体地说,是在无序数组中查找满足特定条件(和为目标值)的两个数。

暴力解法1

在这里插入图片描述

最直接的方法是使用两层嵌套循环遍历数组,对于每对元素,检查它们的和是否等于目标值。这种方法的时间复杂度是O(n^2),其中n是数组的长度,对于大数据集来说效率很低。

func twoSum1(nums []int, target int) []int {for i := 0; i < len(nums); i++ {for j := 0; j < len(nums); j++ {if i == j { // 因为题目中不能使用两次相同的元素continue}if nums[i]+nums[j] == target {return []int{i, j}}}}return nil
}

我们仔细观察下这个两层循环,会发现有重复的比较。

当i=0时,nums[0]=2,2和5、9、4、11进行相加。

当i=1时,nums[1]=5,5和2、9、4、11进行相加。

可以发现nums[1]=5和2相加,已经被计算过了。

当i=2时,nums[2]=9,9和2、5、4、11进行相加。

可以发现nums[2]=9和2、5相加,已经被计算过了。

当i=3时,nums[3]=4,4和2、5、9、11进行相加。

可以发现nums[3]=4和2、5、9相加,已经被计算过了。

下面进行优化,减少重复计算。

暴力解法2

在这里插入图片描述

第二层循环从j开始(j>=i+1)

func twoSum2(nums []int, target int) []int {for i := 0; i < len(nums); i++ {for j := i + 1; j < len(nums); j++ {if nums[i]+nums[j] == target {return []int{i, j}}}}return nil
}

哈希法1:

target=6,当num=2,需要在数组中找出6-2=4,这种查找,哈希最擅长,时间复杂度还是O(1)。

比较常规的方法,先把整个数组建立一个hash表,然后进行查找。

func twoSum3(nums []int, target int) []int {// key:数值,value:下标hashTable := make(map[int]int, 0)for i, num := range nums {hashTable[num] = i}for i := 0; i < len(nums); i++ {if v, ok := hashTable[target-nums[i]]; ok {return []int{i, v}}}return nil
}

哈希法2:

上一个哈希法,可以优化为不提前建立哈希表,在循环的过程中建立哈希。

func twoSum4(nums []int, target int) []int {// key:数值,value:下标nummap := make(map[int]int, 0)for i := 0; i < len(nums); i++ {if v, ok := nummap[target-nums[i]]; ok {return []int{v, i}} else {nummap[nums[i]] = i}}return nil
}

总结:

这个问题的本质是搜索。更具体地说,是在无序或有序数组中查找满足特定条件(和为目标值)的两个数。

这个问题通常可以通过以下几种方式解决,每种方式都体现了不同的算法思想和技巧:
暴力法(Brute Force)
//最直接的方法是使用两层嵌套循环遍历数组,对于每对元素,检查它们的和是否等于目标值。这种方法的时间复杂度是O(n^2),其中n是数组的长度,对于大数据集来说效率很低。
哈希表(Hash Table)
更高效的方法是使用哈希表来记录遍历过的元素和它们的索引。遍历数组时,对于每个元素,我们检查目标值减去当前元素的结果是否已经在哈希表中。如果在,说明我们找到了满足条件的两个数;如果不在,将当前元素及其索引添加到哈希表中。这种方法的时间复杂度是O(n),其中n是数组的长度,因为它只需要遍历数组一次。
双指针法(Two Pointers)
(当数组有序时):如果数组是有序的,我们可以使用双指针法。一个指针从头开始,另一个指针从尾开始。根据两个指针所指向元素的和与目标值的大小关系,移动较小的那个指针(如果和小于目标值,移动头指针;如果和大于目标值,移动尾指针)。这种方法的时间复杂度也是O(n),但它要求数组必须是有序的。

思考题
如果 nums 是有序的,是否还需要哈希表?
如果要求寻找三个数,它们的和等于 target 呢?

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

代码随想录(day8)—环形链表

题目 预备知识点&#xff1a; for和while的区别 while语句属于循环语句&#xff0c;在判断是&#xff0c;如果条件为true&#xff0c;则会继续判断&#xff0c;直到false为止&#xff0c;即会进行多次判断&#xff08;除非一开始条件就是错的&#xff09;。 if语句属于条件判…

【Material-UI】Slider中的 Continuous Sliders 与 Sizes 详解

文章目录 一、Slider 组件概述1. 组件介绍2. 使用场景 二、Continuous Sliders 的详解1. Continuous Sliders 的作用2. Continuous Sliders 的基本用法3. 禁用状态下的 Continuous Sliders4. Continuous Sliders 的实际应用5. Continuous Sliders 的优缺点 三、Slider 的尺寸控…

005-CircuitBreaker断路器-Resilience4J

文章目录 1 CircuitBreaker1.1 实现原理1.2 一句话 2 Resilience4J2.1 是什么2.2 能干嘛2.3 怎么用 3 熔断(CircuitBreaker)(服务熔断服务降级)3.1 断路器三大状态3.2断路器3大状态之前的转换3.3断路器所有配置参数参考3.4 熔断降级案例需求说明3.5 COUNT_BASED(计数的滑动窗口…

科讯档案管理系统存在SQL注入漏洞(0day)

漏洞描述 安徽科迅教育装备20年来来始终坚持智慧校园集成方案产品的开发和部署应用&#xff0c;我们有完善的智慧校园和数字校园建设方案&#xff0c;根据不同的学校不同的实际情况量身定做系统集成方案。产品主要是为了实现校园的智慧网络、智慧OA、智慧教学、智慧学习、数字医…

整理了100个Python精选库,建议收藏!

Python为啥这么火&#xff0c;这么多人学&#xff0c;就是因为简单好学&#xff0c;功能强大&#xff0c;整个社区非常活跃&#xff0c;资料很多。而且这语言涉及了方方面面&#xff0c;比如自动化测试&#xff0c;运维&#xff0c;爬虫&#xff0c;数据分析&#xff0c;机器学…

三. Spring Boot 当中的“容器功能” 和 “配置绑定” 的详细剖析(附+源代码流程)

三. Spring Boot 当中的“容器功能” 和 “配置绑定” 的详细剖析(附源代码流程) 文章目录 三. Spring Boot 当中的“容器功能” 和 “配置绑定” 的详细剖析(附源代码流程)1. Spring Boot 是继续支持了 Spring 当中的注解的1.2 Spring 当中的 Component&#xff0c;Controller…

Unraid 手动安装docker

目录 常用镜像链接一.安装示例1[firefox浏览器]:1.离线下载docker镜像2.将xxx.tar镜像数据加载到 Docker 中3.手动添加docker 二.安装示例2[等我有东西需要安装再回来补教程吧]:三.获取UDI和GID 常用镜像链接 特别版 emby 文件管理器 filebrowser内外穿透 zerotierNAS媒体库管…

JavaEE 第16节 线程安全的集合类

目录 前言 顺序表 队列 哈希表 1、Hashtable 2、ConcurrentHashMap&#xff08;重点&#xff09; 前言 本文章主要介绍在多线程环境下&#xff0c;如何线程安全的使用一些常用的集合类&#xff08;顺序表和哈希表&#xff09;。 顺序表 1、自己使用同步锁机制&#xff…

大数据技术

4v特点 volume&#xff08;体量大&#xff09; velocity&#xff08;处理速度快&#xff09; variety&#xff08;数据类型多&#xff09; value&#xff08;价值密度低&#xff09; 核心设计理念 并行化 规模经济 虚拟化 分布式系统满足需求 系统架构 大数据处理流程 结构化…

CocosCreator 3.8 IOS 热更新失败问题解决方案

CocosCreator 3.8 IOS 热更新失败问题解决方案 问题描述 Creator 版本&#xff1a; 3.8.0目标平台&#xff1a; ios 模拟器/真机重现方式&#xff1a;安卓构建版本生成的热更新包&#xff0c;上传到OSS&#xff0c;使用ios进行更新。 19:18:36 [ERROR]: [ERROR] file /Applica…

动态读取nacos中修改的项目配置文件

本项目用的还是springboot项目&#xff0c;咱们直接上代码 一&#xff1a;首先看下nacos中需要动态获取的属性 二&#xff1a;把需要动态读取的配置类中的属性整理一个实体类 mport lombok.Data; import org.springframework.boot.context.properties.ConfigurationPropert…

PyCharm汉化:简单一步到胃!PyCharm怎么设置中文简体

最近在弄python的项目 一起加油哦 步骤&#xff1a; PyCharm的汉化可以通过两种主要方法完成&#xff1a; 方法一&#xff1a;通过PyCharm内置的插件市场安装中文语言包 1. 打开PyCharm&#xff0c;点击File -> Settings&#xff08;在Mac上是PyCharm -> Preferences…

[报错] nvcc -V 找不到

报错&#xff1a; nvcc : 无法将“nvcc”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。请检查名称的拼写&#xff0c;ObjectNotFound: (nvcc:String) [], CommandNotFoundExceptionFullyQualifiedErrorId : CommandNotFoundException 找不到 nvcc -V&#xff0c;试过…

erlang学习:用OTP构建系统1

书上案例学习并测试 23.1 通用事件处理 -module(event_handler). %% API -export([make/1, add_handler/2, event/2]).%% 制作一个“什么都不干”的事件处理器Name&#xff08;一个原子&#xff09;。这样消息就有地方发送了。 make(Name) ->register(Name, spawn(fun() -…

SoftMaker Office Pro 2024:高效办公的全方位解决方案

SoftMaker Office Pro 2024是一款集高效、专业、全面于一体的办公软件套件&#xff0c;专为满足现代办公需求而设计。这款套件不仅包含了文字处理、电子表格、演示文稿等核心功能&#xff0c;还集成了项目管理、文档管理和客户管理等实用工具&#xff0c;为用户提供了全方位的办…

微前端集成优化:让所有子应用体积更小,加载更快!

简介 随着前端的日益发展&#xff0c;微前端架构越来越受到青睐。它通过将前端应用拆分为多个独立的子应用&#xff0c;每个子应用可以独立开发、部署和运行&#xff0c;从而提升了开发效率和团队协作。目前主流的微前端方案应该是qiankun了。 以笔者公司为例&#xff0c;采用…

Go锁 详解

锁 - Go 函数并发编程中&#xff0c;锁是一种同步机制&#xff0c;用于协调对共享资源的访问&#xff0c;防止数据竞争 - Go 中提供了多种类型的锁&#xff0c;每种锁都有不同的特性和适用场景类型 互斥锁&#xff08;mutex&#xff09; 基础锁&#xff0c;只能同时允许一个 g…

okhttp异步请求连接阻塞问题排查

表现&#xff1a; 使用okhttp请求外部大模型接口时&#xff0c;当并发在2-5左右&#xff0c;出现请求被阻塞在建立http连接之前&#xff0c;阻塞时间超长&#xff08;>20s&#xff0c;从日志看有160s存在&#xff09;。但是httpconfig的connTimeout时间配置为100s&#xff…

python如何调用函数库

python对函数库引用的第一种方式 格式是&#xff1a; import<库名> 例如&#xff1a; import turtle 如果需要用到函数库中函数&#xff0c;需要使用&#xff1a; <库名>.<函数名> 例如&#xff1a; import turtleturtle.fd(100) python对函数库引用的第…

【Qt】网格布局管理器QGridLayout

网格布局管理器QGridLayout Qt中提供QGridLayout用来实现网格布局的效果。 核心属性 整体和 QVBoxLayout 以及 QHBoxLayout 相似. 但是设置 spacing 的时候是按照垂直⽔平两个 ⽅向来设置的. 属性说明 layoutLeftMargin 左侧边距 layoutRightMargin 右侧边距 layoutTo…