LeetCode 热题HOT100-两数之和（C语言）
作为一名程序语言的学习者，刷力扣我想是必要经历的一条路，所以我也在这里分享刷题后所得知识，也可以帮助更多人理解题意。
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
唯For熟尔
可以看到题意中给了一个整数数组nums和目标值target
要求在数组里面找出两个数来实现 x+y=target
1.首先先观察所提供的代码
额外条件：给出了数组的长度 numsSize
还有一个我们暂时不知道用处的 int* returnSize(后面再看)
2.再注意看这段示例，很明显是返回了一个数组来存储nums中两个数的下标
那没什么说法，开空间整就完了
int *a = (int*)malloc(sizeof(int)*2);
到这里就分析得差不多了，很明显，要对nums进行一次遍历，找到合适的数，那万年不变我们就用for来解决，我们只会for，也是没有问题的，遍历出两个数，自然要两个for，就定义两个变量来实现
int i,j; for(i=0;i<numsSize;i++){ for(j=i+1;j<numsSize;j++){ } }
因为两个数不能重复出现，也就是不允许 x+x=target 即数组第一个数不可能再从 i
出发，而数组最后一个数也没必要再与任何一个数组合，这时候我们就可以直接令 j=i+1
省去判断两个数是否相等的步骤，而且当i位于倒数第二个数时，j处于最后一个数，又可以再减少一个步骤。
运用if找到那两个天选之子，填充好代码
int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int *a = (int*)malloc(sizeof(int)*2); /*整一个数组出来*/ int i,j; for(i=0;i<numsSize;i++){ for(j=i+1;j<numsSize;j++){ if(nums[i]+nums[j] == target){ /*判断条件对应题意*/ a[0] = i; a[1] = j; *returnSize = 2; return a; } } } return 0; }
- 到这里我们来填回上面留下的一个坑：returnSize有何作用？
我们可以思考一下，我们是不是要返回两个已经存到了a[ ]这个数组的两个数，那就可以在这里结尾用returnSize表示我要返回的a[ ]的长度，同时后面为什么等于2就解释得通了
数组里面没有结束符号，它得知道你的数组长度才能判断内容
当然可能不理解为什么要出现在循环里，其实，我们放在外边也是可以的，在创建时就把这事解决了
int* twoSum(int* nums, int numsSize, int target, int* returnSize){ int *a = (int*)malloc(sizeof(int)*2); *returnSize = 2; /*放在这里也是没有问题的，运行成功*/ int i,j; for(i=0;i<numsSize;i++){ for(j=i+1;j<numsSize;j++){ if(nums[i]+nums[j] == target){ a[0] = i; a[1] = j; return a; } } } return 0; }
哈希表
/** * Note: The returned array must be malloced, assume caller calls free(). */ // 哈希节点 typedef struct { int key; int value; UT_hash_handle hh; } hash_node; int* twoSum(int* nums, int numsSize, int target, int* returnSize){ int* ans = (int*)malloc(sizeof(int) * 2); // 题目给出答案唯一 所以只有2个下标 if (NULL == ans) exit(-1); *returnSize = 2; // 返回数组大小赋值 // head为头节点 hash_node* head = NULL, *cur, *tmp; // 循环nums把 target - nums[i] 存入哈希表 for (int i = 0; i < numsSize; i++) { hash_node* tmp = NULL; HASH_FIND_INT(head, nums + i, tmp); // 查表 if (NULL != tmp) { // 如果 当前nums[i]元素在哈希表，说明之前已经找到了另一半 ans[0] = tmp->value; // 取出之前下标 ans[1] = i; // 当前下标 break; } // 不在哈希表就把 target - nums[i] 存入哈希表 tmp = (hash_node*)malloc(sizeof(hash_node)); if (NULL == tmp) exit(-1); tmp->key = target - nums[i]; tmp->value = i; HASH_ADD_INT(head, key, tmp); } // 释放哈希表所有节点 HASH_ITER(hh, head, cur, tmp) { HASH_DEL(head, cur); free(cur); } return ans; }
哈希表代码中已经有了注释，可以仔细看看。这道题在这里就告一段落了
希望大家给个三连
给个关注（回关）你们的支持就是我最大的动力！
