力扣|找出和所对应的两数的下标
从零开始刷力扣(bushi
题目放在这:
给定一个整数数组 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]
提示:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
放一个分割线在这:
我自己也是C语言复建,没有系统学习过数据结构,所以第一反应真就是暴力破解(见笑了)
也就是依次将数组的两个元素相加,和目标数做对比
因为只有一个有效答案,那么就可以在检索到和等于目标数数,直接输出对应的坐标
如果遍历结束没有得到结果,则输出NULL
借一下leecode的标准答案,这边我自己加上了前期的输入输出语句,这样方便看到结果:
#include <stdio.h>
#include <stdlib.h>int *twoSum(int *nums, int numsSize, int target, int *returnSize);int main() {int *p, *returnSize;int nums[10];int numsSize = 0, target = 0;*returnSize = 2;printf("找出数组中和为目标数的两个元素的下标:\n请输入数组的长度(不超过十)\n");scanf("%d", &numsSize);printf("请输入数组的内容,并用回车分隔\n");for (int i = 0; i < numsSize; i++) {scanf("%d", &nums[i]);}printf("您输入的数组内容为:nums[]=");for (int i = 0; i < numsSize; i++) {printf("%d ", nums[i]);}printf("请输入您的目标数:\n");scanf("%d", &target);p = twoSum(nums, numsSize, target, returnSize);if (p != NULL) {printf("您的目标数对应的坐标下标为:");printf("%d ", p[0]);printf("%d", p[1]);} elseprintf("您的目标数不能被数组中的任何两个数相加得到。");return 0;
}int *twoSum(int *nums, int numsSize, int target, int *returnSize) {for (int i = 0; i < numsSize; ++i) {for (int j = i + 1; j < numsSize; ++j) {if (nums[i] + nums[j] == target) {int *ret = (int *)malloc(sizeof(int) * 2);ret[0] = i, ret[1] = j;*returnSize = 2;return ret;}}}*returnSize = 0;return NULL;
}
简单讲一点:
1、<stdio.h>头文件,翻译为standard input output
程序中用到的scanf、printf,都需要使用标准的输入输出库
2、<stdlib.h>头文件,和存储、空间分配密切相关的一个函数
程序中用到的malloc函数,用来分配内存空间,出自于这个头文件
类似的还有calloc、free、realloc函数等,感兴趣的可以看一看
3、malloc函数:
函数原型:void * malloc(unsigned size);
功能是分配size字节的存储区。程序中需要两个int的空间所以乘2
默认的类型是void*,由于我设定了ret为int*类型,所以这里强制类型转换为int*
(leecode标准答案是没有这个强制转换的,其实我也有印象这一步可以自动转换,但是我用的Dev C++报错)
再放一个分割线:
那么肯定不可能就到此为止了,在今年校招(2024届校招)中,不知道大家有没有关注腾讯的招聘,直播间提到的就是这个问题。
不过大佬显然指的是用哈希表
什么是哈希表?
哈希表是一种数据结构,提供了快速的插入操作和查找操作
不管哈希表有多少数据,插入和查找的时间复杂度都是O(1),查找速度非常快
不过,哈希表基于数组,一旦数组被填满,性能就大不如前。
关于哈希表,推荐一个视频:
『教程』哈希表是个啥?_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1qR4y1V7g6/?spm_id_from=333.337.search-card.all.click&vd_source=86629babf8e8eb6ebc7b7475ab3f61a2简单理解为:用时间换空间
先放代码(后面有详细解释,这里方便想自学的大佬):
struct hashTable {int key;int val;UT_hash_handle hh;
};struct hashTable* hashtable;struct hashTable* find(int ikey) {struct hashTable* tmp;HASH_FIND_INT(hashtable, &ikey, tmp);return tmp;
}void insert(int ikey, int ival) {struct hashTable* it = find(ikey);if (it == NULL) {struct hashTable* tmp = malloc(sizeof(struct hashTable));tmp->key = ikey, tmp->val = ival;HASH_ADD_INT(hashtable, key, tmp);} else {it->val = ival;}
}int* twoSum(int* nums, int numsSize, int target, int* returnSize) {hashtable = NULL;for (int i = 0; i < numsSize; i++) {struct hashTable* it = find(target - nums[i]);if (it != NULL) {int* ret = malloc(sizeof(int) * 2);ret[0] = it->val, ret[1] = i;*returnSize = 2;return ret;}insert(nums[i], i);}*returnSize = 0;return NULL;
}
然后咱们就来详细解释这个代码。
已知,用哈希表查询,首先将要查找的东西作为参数进入一个函数,得到一个确定的数字
该数字就是哈希表中,查询结果的地址。
这样,本来我们需要一个个查询、比较的,现在只需要经过一次函数计算,一次查找。
将目光回到代码上:
struct hashTable {int key;int val;UT_hash_handle hh;
};
给出哈希表的结构,这个在哈希表的使用中是确定的,一般第一个是数值,第二个是位置(原本数组中的位置),第三个是一个句柄,链接前一个和后一个哈希表
struct hashTable* hashtable;struct hashTable* find(int ikey) {struct hashTable* tmp;HASH_FIND_INT(hashtable, &ikey, tmp);return tmp;
}
建立一个哈希表的指针,并且设置一个寻找函数
输入参数是我们要找的结果,并内置了HASH_FIND_INT函数
这个是头文件中包含的函数,主要参数有三个,
第一个就当默认参数,第二个是要找的值,第三个是哈希表的指针(做返回值用)
该函数的意义是:
找到ikey对应的值,如果哈希表中没有,tmp=NULL
如果找到了对应的值,tmp的第一个值为ikey,第二个是ikey对应的哈希表的val
简单来说就是一个查询操作,如果没有返回NULL,如果有返回对应的数值和位置
void insert(int ikey, int ival) {struct hashTable* it = find(ikey);if (it == NULL) {struct hashTable* tmp = malloc(sizeof(struct hashTable));tmp->key = ikey, tmp->val = ival;HASH_ADD_INT(hashtable, key, tmp);} else {it->val = ival;}
}
定义一个插入函数
find函数就是我们上面提到的寻找函数,会返回一个哈希表的指针,
如果返回的指针为NULL,也就是哈希表中没有我们要找的值,会再次定义一个分配了一个哈希表空间的指针tmp,并将对应的数值,以及数值在原本数组中的数值赋值给新建的哈希表
运用HASH_ADD_INT函数将这个新建的数据增加到哈希表中
如果返回的指针有数值,也就是哈希表中已经存在对应的结果了,找到了,那就更方便,直接记录
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {hashtable = NULL;for (int i = 0; i < numsSize; i++) {struct hashTable* it = find(target - nums[i]);if (it != NULL) {int* ret = malloc(sizeof(int) * 2);ret[0] = it->val, ret[1] = i;*returnSize = 2;return ret;}insert(nums[i], i);}*returnSize = 0;return NULL;
}
这是函数的主体
按照原始数组的顺序循环,依次查找target-nums[i]的结果,刚开始都是向哈希表内添加数,直到找到对应的结果
因为这里假设只存在唯一解,所以就没有必要考虑多种情况
简单画一个执行的逻辑吧:
相关文章:

力扣|找出和所对应的两数的下标
从零开始刷力扣(bushi 题目放在这: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值target的两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一…...

使用命令行创建仓库
如果你还没有任何代码,可以通过命令行工具创建一个全新的Git仓库并初始化到本项目仓库中。 git clone https://e.coding.net/***/neurosens.git cd neurosens echo "# neurosens" >> README.md git add README.md git commit -m "first commi…...

ESLint 中的“ space-before-function-paren ”相关报错及其解决方案
ESLint 中的“ space-before-function-paren ”相关报错及其解决方案 出现的问题及其报错: 在 VScode 中,在使用带有 ESLint 工具的项目中,保存会发现报错,并且修改好代码格式后,保存会发现代码格式依然出现问题&…...

docker常用中间件安装
文章目录 1、前言2、中间件安装2.1、mysql2.2、gitlab容器2.3、nacos2.4、redis2.5、xxljob2.6、zipkin2.7、sentinel2.8、seata2.8.1、获取镜像2.8.2、运行容器并获取配置 2.9、rockerMQ2.9.1、rockerMQ-namesrv2.9.2、rockerMQ-broker2.9.3、rockerMQ-console 2.10、jenkins2…...
Camunda 7.x 系列【44】修改流程实例
有道无术,术尚可求,有术无道,止于术。 本系列Spring Boot 版本 2.7.9 本系列Camunda 版本 7.19.0 源码地址:https://gitee.com/pearl-organization/camunda-study-demo 文章目录 1. 概述2. 案例演示2.1 回退2.2 子流程2.3 多实例加签1. 概述 流程模型中,执行活动需要按…...

无频闪护眼灯哪个好?什么是无频闪
随着科技的不断发展,工作时使用电子设备越来越普遍,如何保护我们的眼睛不受蓝光、频闪等危害就变得极其重要了。护眼台灯,顾名思义就是保护眼睛的台灯,其工作原理是在光源处使用特殊的防蓝光灯珠,并通过控制电流的稳定性来达到防频…...

css网格布局
css网格布局 常用属性 display: grid; //开启网格grid-template-columns: 2fr 1fr 1fr 1fr 1fr; //设置多少列每列宽度grid-gap: 10px; // 设置表格之间间距grid-template-rows: 50px 50px 50px 50px; // 设置多少行 每行的高度grid-column : 1 //占据位置 占据1格grid-colu…...
Hadoop -HDFS常用操作指令
1.启动HDFS hadoop/sbin/start-dfs.sh2.关闭 HDFS hadoop/sbin/stop-dfs.sh3. 在HDFS中创建文件夹 #老版本 hadoop fs -mkdir -p path #新版本 hadoop dfs -mkdir -p path4.查看指定目录下内容 hadoop fs -ls [-h] [-R] path hadoop dfs -ls [-h] [-R] ptahpath 指定…...
代码随想录二刷day11
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、力扣20. 有效的括号二、力扣1047. 删除字符串中的所有相邻重复项三、力扣150. 逆波兰表达式求值 前言 一、力扣20. 有效的括号 class Solution {public bo…...

系统架构技能之设计模式-工厂模式
一、开篇 本文主要是讲述设计模式中最经典的创建型模式-工厂模式,本文将会从以下几点对工厂模式进行阐述。 本文将会从上面的四个方面进行详细的讲解和说明,当然会的朋友可以之处我的不足之处,不会的朋友也请我们能够相互学习讨论。 二、摘…...

Docker的基本组成和安装
Docker的基本组成 镜像(image): docker镜像就好比是一个模板,可以通过这个模板来创建容器服务,tomcat镜像 > run > tomcat01容器(提供服务) 通过这个镜像可以创建多个容器(最…...

【python爬虫】15.Scrapy框架实战(热门职位爬取)
文章目录 前言明确目标分析过程企业排行榜的公司信息公司详情页面的招聘信息 代码实现创建项目定义item 创建和编写爬虫文件存储文件修改设置 代码实操总结 前言 上一关,我们学习了Scrapy框架,知道了Scrapy爬虫公司的结构和工作原理。 在Scrapy爬虫公司…...

Apinto 网关 V0.14 版本发布,6 大插件更新!
大家好! 距离上次更新已经过去一段时间了,这段日子里我们一直在酝酿新的功能,本次的迭代将给大家带来 6 大插件的更新~一起来看看有哪些变化吧! 新特性 1. 新增 额外参数v2 插件,支持对转发参数进行加密、拼接等操作…...

突破销售瓶颈:亚马逊卖家如何借力TikTok网红营销?
随着社交媒体的崛起,营销方式也在不断变革。TikTok作为一款风靡全球的短视频平台,吸引了数以亿计的用户,成为了品牌宣传和销售的新热点。对于亚马逊卖家而言,通过合理运用TikTok网红营销策略,可以有效提升产品的曝光度…...
JavaWeb之Cookie的简单使用!!!
什么是Cookie Cookie:客户端会话技术,将数据保存到客户端,以后每次请求都携带Cookie数据进行访问 Cookie 数据存放在浏览器端(客户端) 创建Cookie 1.创建Cookie Cookie cookie new Cookie("key","value"); 2.使用response响应…...

16、Flink 的table api与sql之连接外部系统: 读写外部系统的连接器和格式以及Apache Hive示例(6)
Flink 系列文章 1、Flink 部署、概念介绍、source、transformation、sink使用示例、四大基石介绍和示例等系列综合文章链接 13、Flink 的table api与sql的基本概念、通用api介绍及入门示例 14、Flink 的table api与sql之数据类型: 内置数据类型以及它们的属性 15、Flink 的ta…...

6.Redis-hash
hash 哈希类型中的映射关系通常称为field-value,⽤于区分 Redis 整体的键值对(key-value),注意这⾥的value是指field对应的值,不是键(key)对应的值,请注意 value 在不同上下⽂的作⽤…...
点云从入门到精通技术详解100篇-多时相机载激光雷达人工林点云匹配及生长监测(续)
目录 多时相机载激光雷达人工林点云匹配及变化监测 3.1 技术路线 3.2 数据准备 3.3 方法...
【Vue3 知识第七讲】reactive、shallowReactive、toRef、toRefs 等系列方法应用与对比
文章目录 一、reactive()二、readonly()三、shallowReactive()四、shallowReadonly()五、isReactive() 和 isReadonly()六、toRef()七、toRefs()八、toRaw()九、ref、toRef、toRefs 异同点 一、reactive() reactive() 函数用于返回一个对象的响应式代理。与 ref() 函数定义响应…...
Docker 摸门级简易手册
Docker 摸门级简易手册 文章目录 Docker 摸门级简易手册使用 Docker 构建 Java 项目镜像Docker 安装Install on MacInstall on WindowsInstall on Linux Dockerfile 说明FROMLABELENVWORKDIRCOPYADDRUNCMDEXPOSEENTRYPOINTVOLUMEUSER 使用 Docker 构建 Java 项目镜像 假设有个…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...

STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

【iOS】 Block再学习
iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...

【汇编逆向系列】六、函数调用包含多个参数之多个整型-参数压栈顺序,rcx,rdx,r8,r9寄存器
从本章节开始,进入到函数有多个参数的情况,前面几个章节中介绍了整型和浮点型使用了不同的寄存器在进行函数传参,ECX是整型的第一个参数的寄存器,那么多个参数的情况下函数如何传参,下面展开介绍参数为整型时候的几种情…...

Web APIS Day01
1.声明变量const优先 那为什么一开始前面就不能用const呢,接下来看几个例子: 下面这张为什么可以用const呢?因为复杂数据的引用地址没变,数组还是数组,只是添加了个元素,本质没变,所以可以用con…...

AI书签管理工具开发全记录(十八):书签导入导出
文章目录 AI书签管理工具开发全记录(十八):书签导入导出1.前言 📝2.书签结构分析 📖3.书签示例 📑4.书签文件结构定义描述 🔣4.1. 整体文档结构4.2. 核心元素类型4.3. 层级关系4.…...
Python打卡训练营学习记录Day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...