【算法】两数之和（暴力求解+哈希表）
本题来源---《两数之和》。
题目描述
给定一个整数数组 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 = i+1; 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：即题中给定的整数数组，
（2）numSize：即该整数数组大小，
（3）target：即给定的整数目标值，
（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作为key，ival作为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是数组中的元素数量。主要为哈希表的开销。
第一次做算法题，有很多不足与欠缺，欢迎大家与我讨论！