<p# 1. 两数之和
## 题目
给定一个整数数组 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]
## 提示
* 2 <= nums.length <= 104
* -109 <= nums[i] <= 109
* -109 <= target <= 109
* 只会存在一个有效答案
## 进阶
你可以想出一个时间复杂度小于 O(n2) 的算法吗？
## 解题思路
最直接的思路是暴力枚举，时间复杂度为O(n^2)，空间复杂度为O(1)。
为了降低时间复杂度，我们可以使用哈希表，将寻找target – x的时间复杂度从O(n)降低到O(1)。这样时间复杂度为O(n)，空间复杂度为O(n)。
具体地，创建一个哈希表，对于每一个x，首先查询哈希表中是否存在target – x，然后将x插入到哈希表中，即可保证不会让x和自己匹配。
## 代码
c
/** * Note: The returned array must be malloced, assume caller calls free(). */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) { for (int i = 0; i < numsSize; i++) { for (int 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;
}
c
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); return tmp;
}
void insert(int ikey, int ival) { struct hashTable* it = find(ikey); if (it == NULL) { struct hashTable* tmp = malloc(sizeof(struct hashTable)); 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 val, ret[1] = i; *returnSize = 2; return ret; } insert(nums[i], i); } *returnSize = 0; return NULL;
}
## 复杂度
暴力枚举：
* 时间复杂度：O(n^2)
* 空间复杂度：O(1)
哈希表：
* 时间复杂度：O(n)
* 空间复杂度：O(n)
