本文主要是介绍「LeetCode」1.两数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题目来源：力扣（LeetCode），链接：https://leetcode-cn.com/problems/two-sum
解题思路:
- 暴力法：嵌套循环，固定一个数，然后在后面度部分进行查找，时间复杂度是O(n^2)，
- 一遍哈希法：建立一个哈希表，哈希表中，值为key，位置为value。遍历的时候，先去查找target - nums[i] 是否在哈希表中，如果在的话直接返回结果，如果不在的话。将当前值加入哈希表中。
C语言代码如下，使用https://troydhanson.github.io/uthash/提供的哈希表，不再额外造轮子
/*** Note: The returned array must be malloced, assume caller calls free().*/struct hashtable {int key; /* key */int value;UT_hash_handle hh; /* makes this structure hashable */
};void add(struct hashtable **table, int num, int idx) {//申请一个结构存放数据struct hashtable *s;s = malloc(sizeof(struct hashtable));s->key = num;s->value = idx;HASH_ADD_INT((*table), key, s ); /* id: name of key field */
}//一遍哈希法
// 从头往后遍历，检查target - nums[i] 是否在hash表中
// 如果不在, 以值为key，下标为value进行存放
int* twoSum(int* nums, int numsSize, int target, int* returnSize){struct hashtable *table = NULL; //新建哈希表 struct hashtable *tmp; //用于存放找到中间结果*returnSize = 2;int *res = (int*)malloc(sizeof(int) * *returnSize);int remain;for(int i = 0; i < numsSize; i++){remain = target - nums[i]; //剩余值// 在表table中查找remin, 如果有结果，返回tmpHASH_FIND_INT(table, &remain, tmp);if ( tmp == NULL ){add(&table, nums[i], i);} else {res[1] = i;res[0] = tmp->value;break;}}return res;}
这篇关于「LeetCode」1.两数之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
