景观设计网站推荐,北京sem,wordpress站点app开发,网站云模板从零开始刷力扣#xff08;bushi
题目放在这#xff1a;
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出和为目标值target的两个整数#xff0c;并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一…从零开始刷力扣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.hint *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届校招中不知道大家有没有关注腾讯的招聘直播间提到的就是这个问题。
不过大佬显然指的是用哈希表
什么是哈希表
哈希表是一种数据结构提供了快速的插入操作和查找操作
不管哈希表有多少数据插入和查找的时间复杂度都是O1查找速度非常快
不过哈希表基于数组一旦数组被填满性能就大不如前。
关于哈希表推荐一个视频
『教程』哈希表是个啥_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1qR4y1V7g6/?spm_id_from333.337.search-card.all.clickvd_source86629babf8e8eb6ebc7b7475ab3f61a2简单理解为用时间换空间
先放代码后面有详细解释这里方便想自学的大佬
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对应的值如果哈希表中没有tmpNULL
如果找到了对应的值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]的结果刚开始都是向哈希表内添加数直到找到对应的结果
因为这里假设只存在唯一解所以就没有必要考虑多种情况
简单画一个执行的逻辑吧
