百度注册页面,深圳seo优化服务,wordpress中文版 docker,淘宝运营培训班去哪里学一、题目描述
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一个元素在答案里不能重复出现。
你可以…一、题目描述
给定一个整数数组 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 只会存在一个有效答案
进阶你可以想出一个时间复杂度小于 O(n2) 的算法吗
二、思路
1. 最直接能想到的就是暴力解法将数组中的每一个数据俩俩匹配、计算出和当和等于目标值时返回俩个数据的数组下标。双for嵌套循环代码略。
2. 因为对于数组数据x寻找数据target-x的复杂度过高可以使用哈希算法来降低其寻找复杂度。做法是根据题目数组数量及数值范围确定哈希函数及哈希表的实现方法根据题意从数组下标0开始遍历数组遍历到数组数据为x时先使用key为target-x在哈希表中查找对应值如果没找到将数据x以key为x存放在哈希表的对应位置。若找到哈希表中value值不为Null即配对成功此时输入的数组中存在当前位置的x和target -x由于我的算法没有记录target-x的数组对应下标在输出时再遍历一次数组找出target-x对应的数组下标联合当前位置x的数组下标组成return数组。
三 代码
/*** Note: The returned array must be malloced, assume caller calls free().*/#define Null 0x3f3f3f3f // 定义哈希表的初始值即未赋值的状态。
int hash[20001]; // 数组长度最大为10000定义哈希表长度为20000可获取较好的性能int find_flag(int *nums, int numsSize, int x) { // 找出target-x对应的数组下标int i 0;while (i numsSize) {if (nums[i] x) return i;i;}return -1;
}int find(int x){ // 哈希算法取余 数组hash为哈希表输入的x为哈希表的keya[x]为哈希表的值int i (x % 20001 20001) % 20001; // 将输入的keykey就是x值经过算法分布在0-20000之间while (hash[i] ! Null hash[i] ! x) { // 1.当哈希表中value等于Null可返回哈希表下标i ; // 2.当哈希表对应位置已被赋值且value值不等key发生哈希碰撞i往哈希表后方一直寻找空位(value值为Null)(20000个位置一定可以找到)。 if (i 2 * 10010) i 0;}return i;
}int* twoSum(int* nums, int numsSize, int target, int* returnSize) {memset(hash, 0x3f, sizeof(hash));int tmp,i 0;for (i 0; i numsSize; i ) {int x find(target - nums[i]); // 先找target-x是否能在hash表中找到数据。if (hash[x] ! Null) { // 能找到的话返回当前位置和target-x的位置* returnSize 2;int *ret (int *)malloc(2 * sizeof(int));ret[0] i;ret[1] find_flag(nums, numsSize, target - nums[i]);return ret;} else if (hash[x] Null) { // 没找到则以x为hash key存入哈希表中待匹配x find(nums[i]); // 经过hash算法找出key值对应下标hash[x] nums[i]; // 根据对应下标在hash表中赋值} else {printf(hash crash, modify hash fuction\n);}}return NULL;
}四、结果
使用C语言需要自己手动完成hash表坏处是代码量较大写法较多较为复杂。好处是可以根据不同的场景去调整hash算法达到更高的效率。整体思路还是使用了空间换时间的思想。使用二维数组可以将输入hash表的key对应数组下标也保存在hash表内。可以进一步利用空间来压缩时间免去最后因为寻找target-x的下标而遍历数组。
