给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
方法一
基本思路:暴力枚举,根据两数求和的关系,枚举遍历数组
学习malloc()动态分配的用法。为什么要使用malloc(),而不是直接创建一个数组呢。
第一,在函数中创建的数组,在函数外其内容会被清除,也就是局部变量
第二,malloc()会在内存池中为ret分配一个地址,存储于其中的内容不受作用域的影响,除非使用free()函数,释放内存。
malloc()的返回值是一个指针,此外,若内存不在使用,应free();
int* twoSum(int* nums, int numsSize, int target, int* returnSize){ int i,j; for(i = 0; i < numsSize; i++) { for(j = i+1; j < numsSize; j++) { if(*(nums + i) + *(nums + j) == target) { int *ret = malloc(sizeof(int) * 2); ret[0] = i; ret[1] = j; *returnSize = 2; return ret; } } } *returnSize = 0; return NULL; }
方法二
基本思路:使用哈希表,对于每一个 x
,我们首先查询哈希表中是否存在 target - x
,然后将 x
插入到哈希表中,即可保证不会让 x
和自己匹配。
struct hashTable { int key; int val; UT_hash_handle hh; }; struct hashTable* hashtable;
/*参数 ikey 键
作用 在哈希表中寻找键
返回值 返回待插入的键值对结构体,是指针形式。它的key和value都要给定了。 struct hashTable* find(int ikey) { struct hashTable* tmp; //这里只是一个同名的局部变量 HASH_FIND_INT(hashtable, &ikey, tmp); return tmp; } /*参数 ikey 键
ival 值
作用 在哈希表中寻找键,若不存在,则插入
若存在,测更新信息
*/ void insert(int ikey, int ival) { struct hashTable* it = find(ikey); if (it == NULL) { struct hashTable* tmp = malloc(sizeof(struct hashTable)); //malloc分配内存后,会一直存在 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; } 作者:力扣官方题解 链接:https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
C语言哈希表库:C语言小知识——uthash使用_uthash判断元素是否存在_辣椒油li的博客-CSDN博客
标签:struct,nums,int,ret,hashTable,两数,target From: https://www.cnblogs.com/hk-to-try/p/17187566.html