网站建设上传文件,企业网站设计服务公司,淘客自己做网站,活动网页怎么做本题来源---《两数之和》。
题目描述 给定一个整数数组 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]
叫我们一起来看看本道题怎么解决吧 解法一暴力求解 解法二哈希表
解法一暴力求解 通过枚举数组中的每一个数 x寻找数组中是否存在 target - x。主要就是用for循环遍历整个数组的方式寻找 target - x 时需要注意到每一个位于 x 之前的元素都已经和 x 匹配过因此不需要再进行匹配。而每一个元素不能被使用两次所以我们只需要在 x 后面的元素中寻找 target - x。
代码如下
int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{int i,j;for(i 0; i numsSize; i){for(j i1; j numsSize; j){if(nums[i] nums[j] target) //满足条件{*returnSize 2;int *array (int *)malloc(sizeof(int)*2);array[0] i;array[1] j;return array;}}}*returnSize 0;return NULL;
} 这里容易被误解的地方我个人认为是传入参数的意义。 1*nums即题中给定的整数数组 2numSize即该整数数组大小 3target即给定的整数目标值 4*returnSize即所要返回数组的大小。
复杂度分析 时间复杂度O(N^2)其中 N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。 空间复杂度O(1)。
解法二哈希表
图解参考示例 2
共三步
算出当前数字和目标数字target的差值检查哈希表中是否存在该差值存在就返回该结果。不存在当前数字作为key索引作为value存入哈希表 代码如下
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); //查看hashtable中是否存在ikey值存在则返回tmp指向该值不存在则返回NULLreturn tmp;
}void insert(int ikey,int ival){struct hashTable* tmp malloc(sizeof(struct hashTable));tmp-key ikey;tmp-val ival;HASH_ADD_INT(hashtable,key,tmp); //哈希表不存在ikey值将ikey作为keyival作为val存入哈希}int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{int i;hashtable NULL;for(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); //哈希表中不存在该差值当前数字作为key索引作为value存入哈希表}*returnSize 0;return NULL;
}
复杂度分析 时间复杂度O(N)其中 N 是数组中的元素数量。对于每一个元素 x我们可以 O(1)地寻找 target - x。 空间复杂度O(N)其中 N是数组中的元素数量。主要为哈希表的开销。 第一次做算法题有很多不足与欠缺欢迎大家与我讨论
