1. 题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
2. 解法分析
2.1 解法1：双循环
容易想到使用双层for循环来枚举答案的暴力方法解决此问题，但是效率太低下，O(n²)时间复杂度，不适合大数据量
该方法过程如下：
- 构建循环
-
外层循环变量
i从0到numsSize-1 -
内层循环变量
j从i+1到numsSize-1（确保不会重复使用同一个元素）
- 检查数对和:
if(nums[i] + nums[j] == target)-
如果找到满足条件的数对，执行以下操作：
-
设置返回大小
*returnSize = 2 -
动态分配结果数组（两个int）
-
将两个索引存入数组：
result[0]=i,result[1]=j -
直接返回结果数组
- 未找到解的处理:
-
设置
*returnSize = 0 -
返回
NULL
时间复杂度
- O(n²): 最坏情况下需要检查所有n(n-1)/2个数对
空间复杂度
- O(1): 除结果数组外只使用常数空间（结果数组不计入空间复杂度时）
- 无解处理:
-
设置
*returnSize=0并返回NULL是标准做法 -
调用者可通过
returnSize判断是否有解
示例执行过程
输入：nums = [2,7,11,15], target=9
-
i=0(值2),j=1(值7): 2+7=9 → 找到解 -
分配结果数组，设置
result[0]=0,result[1]=1 -
设置
*returnSize=2 -
返回结果数组
[0,1]
2.2 解法二：哈希表
当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。我们首先将所有元素遍历一遍存放到哈希表中，第二次遍历的时候就去哈希表中查询是否有已经遍历过的数和当前遍历的数相加是否等于target。
哈希表版本解题思路：
步骤1：定义哈希表结构
-
使用结构体
map构造哈希表的条目，包含：key: 数组元素的值value: 该元素在数组中的索引
步骤2：实现哈希表基本操作
-
hashMapAdd: 添加或更新键值对。如果键不存在，创建新条目并添加到哈希表；如果存在，则更新其值。 -
hashMapFind: 根据键查找条目，返回条目指针（找不到返回NULL）。 -
hashMapCleanUp: 清理哈希表，释放所有条目内存。
步骤3：实现twoSum函数
a. 初始化全局哈希表指针为NULL（避免之前的数据干扰）。
b. 预分配结果数组ans（两个整数）。
c. 第一次遍历数组：将每个元素的值作为key，索引作为value存入哈希表。
注意：如果遇到相同的元素，后面的索引会覆盖前面的（因为同一个key在哈希表中只能存在一个）。
d. 第二次遍历数组：对于每个元素nums[i]，计算补数complement = target - nums[i]，然后在哈希表中查找补数。
查找成功且满足条件（补数对应的索引不等于当前索引，避免同一个元素用两次）时：
将当前索引i和补数的索引hashMapRes->value存入结果数组。
设置返回数组大小为2，返回结果数组。
e. 如果遍历结束未找到，则清理哈希表并返回NULL。
优势：
哈希表版本的核心思路是“空间换时间”，通过O(n)的额外空间将时间复杂度从O(n²)降低到O(n)。它通过两次遍历完成：
第一次遍历：建立值到索引的映射（哈希表）。
第二次遍历：对于每个元素，检查其补数是否在哈希表中（且不是自身）。
与双层循环法相比，哈希表法更适合处理大规模数据，但需要注意内存泄漏和线程安全问题。
3. C语言代码实现
3.1 双层for循环法
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){*returnSize = 2;int* result = (int*)malloc(2 * sizeof(int));result[0] = i;result[1] = j;return result;}}}*returnSize = 0;return NULL;
}
3.2 哈希表法
typedef struct
{int key;int value;UT_hash_handle hh;
}map;map* hashMap = NULL;void hashMapAdd(int key, int value){map* s;//检查key是否在hash表中HASH_FIND_INT(hashMap, &key, s);if(s == NULL){s = (map*)malloc(sizeof(map));s->key = key;HASH_ADD_INT(hashMap, key, s);}s->value = value;
}map* hashMapFind(int key){map* s;HASH_FIND_INT(hashMap, &key, s);return s;
}void hashMapCleanUp(){map* cur, *tmp;HASH_ITER(hh, hashMap, cur, tmp){HASH_DEL(hashMap, cur);free(cur);}
}void hashPrint(){map* s;for(s = hashMap; s != NULL; s = (map*)(s -> hh.next)){printf("key = %d, value = %d", s->key, s->value);}
}int* twoSum(int* nums, int numsSize, int target, int* returnSize){int i, *ans;//在哈希表里寻找补数map* hashMapRes;hashMap = NULL;ans = malloc(sizeof(int) * 2);for(i = 0; i < numsSize; i++){//key代表nums[i]的值，value代表所在indexhashMapAdd(nums[i], i);}for(i = 0; i < numsSize; i++){hashMapRes = hashMapFind(target - nums[i]);if(hashMapRes && hashMapRes -> value != i){ans[0] = i;ans[1] = hashMapRes -> value;*returnSize = 2;return ans;}}hashMapCleanUp();return NULL;
}
