刷题笔记:力扣第1题-两数之和

2026.3.5（双层循环、排序+双指针）

1.Note: The returned array must be malloced, assume caller calls free().这句话的意思是“注意：返回的数组必须使用 malloc 分配，假设调用者会调用 free()。”也就是说提交的代码里面只需要分配内存，不需要释放内存。

2.原题目给的函数里面的参数，* nums是数组首地址，numsSize是数组长度，target是所要寻找的加和目标值，* returnSize是返回数组的长度（在本题中固定为2）。

3.由于题目说使用的数组需要自行malloc获取内存，所以必不可少的一句代码便是：

int *list = (int *)malloc(2 * sizeof(int));

当获取完内存之后，list就可以看作是一段数组的首地址，数组长度为2。

4.拿到题目，第一个想到的方法便是枚举法，即嵌套两个for循环，遍历数组所有成员，当找寻到目标后返回下标值，初步写的代码如下：

 1. int* twoSum(int* nums, int numsSize, int target, int* returnSize) { 2. int i, j; 3. int *list = (int *)malloc(2 * sizeof(int)); 4. *returnSize = 2; 5. for (i = 0; i < numsSize; i++){ 6. for (j = i + 1; j < numsSize; j++){ 7. if (nums[i] + nums[j] == target){ 8. list[0] = i; 9. list[1] = j; 10. return list; 11. } 12. } 13. } 14. return list; 15. } 

由于list[1]和*(list + 1)完全等价，所以代码中可以做如下替换：

 1. int* twoSum(int* nums, int numsSize, int target, int* returnSize) { 2. int i, j; 3. int *list = (int *)malloc(2 * sizeof(int)); 4. *returnSize = 2; 5. for (i = 0; i < numsSize; i++){ 6. for (j = i + 1; j < numsSize; j++){ 7. if (*(nums + i) + *(nums + j) == target){ 8. *list = i; 9. *(list + 1) = j; 10. return list; 11. } 12. } 13. } 14. return list; 15. } 

5.虽然题目中所说题目一定有解，函数一定会从if中的return出去，但编译器还是会需要代码中最后一行的那个return来兜底，确保函数一定会返回int *类型的值。

6.int *list = (int *)malloc(2 * sizeof(int));这行代码中malloc前面的(int *)在C语言环境下没必要加，虽然malloc返回值为void *，但是void *可以隐式转换为任意其他类型的指针，所以在这里属于冗余。写成如下形式也可行：

int *list = malloc(2 * sizeof(int));

不过为了防止自己粗心导致开辟的空间和创建的指针类型不匹配，平时还是建议加上(int *)强制转换这一步。

7.目前的初步代码的时间复杂度为O(n2)，空间复杂度为O(1)，力扣上最快的答案如下：

 1. int cmp(const void*a, const void* b) { 2. if(*(int*) a > *(int*) b) return 1; 3. return -1; 4. } 5. int* twoSum(int* nums, int numsSize, int target, int* returnSize) { 6. int* ans = malloc(sizeof(int) * 10010); 7. int ans_cnt = 0; 8. int temp[10010]; 9. memcpy(temp, nums, sizeof(int) * numsSize); 10. qsort(nums, numsSize, sizeof(int), cmp); 11. int left = 0, right = numsSize-1; 12. while(left < right) { 13. if(nums[left] + nums[right] == target) { 14. left = nums[left]; 15. right = nums[right]; 16. break; 17. } else if(nums[left] + nums[right] > target) right --; 18. else left ++; 19. } 20. for (int i = 0; i < numsSize; i ++) { 21. if(temp[i] == left) { 22. ans[ans_cnt ++] = i; 23. break; 24. } 25. } 26. for (int i = numsSize-1; i >= 0; i --) { 27. if(temp[i] == right) { 28. ans[ans_cnt ++] = i; 29. break; 30. } 31. } 32. *returnSize = ans_cnt; 33. return ans; 34. } 

可以看到，答案里面使用了qsort函数，这是C语言提供的一种能使用快速排序来对数组进行排序的算法。该函数的介绍如下：

所以在使用qsort之前，需要在开头定义一个比较函数，一般定义为：

int cmpfunc (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } 

使用的时候传入该函数即可：

qsort(values, 5, sizeof(int), cmpfunc);

函数名就是该函数的指针，所以在使用qsort时，最后一个变量传入cmpfunc和&cmpfunc是等价的。

8.代码的时间复杂度取决于主导项，答案每一步的时间复杂度如下：

关于快速排序为什么时间复杂度为O(nlogn)，如下：

9.答案使用的是双指针优化解法，先将原始数组复制一份来保存原始下标，再使用快速排序将原数组排好序，用一左一右两个指针从数组的最小值和最大值开始找，比目标值小就让左边指针右移一位，比目标值大就让右边指针左移一位。找到目标值后跳出循环，开始在原始数组中寻找下标。虽然原始数组没有大小排序关系，但左右指针取得的值还是需要从原始数组一左一右来找，是为了在处理重复元素场景，避免取到同一个下标。

2026.3.12（哈希表）

1.刚刚学习到了哈希表方法，想到力扣第1题也能用哈希表，并且是比较简单的类型，所以来重新写一遍练习哈希表的使用。使用UTHash，创建哈希表节点结构体：

1. typedef struct{ 2. int key; 3. int idx; 4. UT_hash_handle hh; 5. } HashEntry; 

本题适合使用Map类型的哈希表，所以结构体里面一定有键值对。其中key存储键，也就是出现的元素；idx存储对应的值，也就是在原数组的下标；UT_hash_handle hh为UTHash所需的固定字段。

2.算法逻辑为遍历整个数组，使用HASH_FIND_INT来寻找键为整型数据的节点，每次需要寻找的元素为目标值-目前元素值，如果未找到则使用HASH_ADD_INT将当前整型数据元素对应的节点存储进哈希表，如果找到了则将找到的节点存储的下标和当前元素的下标分别传进结果数组中，输出结果数组即可。完整代码如下：

 1. /** 2. * 哈希表节点结构体定义（适配 uthash 库） 3. * key: 存储 nums 数组中的数值（作为哈希表的键） 4. * idx: 存储该数值在 nums 数组中的下标（作为哈希表的值） 5. * hh: uthash 固定字段，用于维护哈希表的桶、链表等结构（无需手动操作） 6. */ 7. typedef struct{ 8. int key; 9. int idx; 10. UT_hash_handle hh; 11. } HashEntry; 12. 13. int* twoSum(int* nums, int numsSize, int target, int* returnSize) { 14. HashEntry* hashTable = NULL; // 初始化哈希表（uthash 要求初始化为 NULL） 15. int* result = (int*)malloc(sizeof(int) * 2); // 分配结果数组内存（固定返回 2 个下标） 16. *returnSize = 2; // 结果数组长度固定为 2，告知调用者返回数组的元素个数 17. 18. // 遍历数组，一边插入哈希表，一边查找目标补数 19. for (int i = 0; i < numsSize; i++){ 20. HashEntry* entry; // 用于接收哈希表查找结果的节点指针 21. int need = target - nums[i]; // 计算当前数的「补数」（target - nums[i]） 22. 23. // 核心：在哈希表中查找是否存在该补数 24. // HASH_FIND_INT 宏参数说明： 25. // 1. hashTable: 待查找的哈希表 26. // 2. &need: 要查找的键（必须传 int* 类型） 27. // 3. entry: 输出参数，找到则指向对应节点，未找到则为 NULL 28. HASH_FIND_INT(hashTable, &need, entry); 29. 30. if (entry == NULL){ 31. // 补数不存在 → 将当前数和下标插入哈希表 32. entry = (HashEntry*)malloc(sizeof(HashEntry)); // 分配新节点内存 33. entry -> key = nums[i]; // 存储当前数值作为哈希键 34. entry -> idx = i; // 存储当前数值的数组下标 35. // HASH_ADD_INT 宏参数说明： 36. // 1. hashTable: 要插入的哈希表 37. // 2. key: 结构体中作为键的字段名（对应 struct 中的 key 字段） 38. // 3. entry: 要插入的节点指针 39. HASH_ADD_INT(hashTable, key, entry); 40. } else { 41. // 补数存在 → 找到答案，填充结果数组并返回 42. result[0] = entry -> idx; // 补数的下标（先插入哈希表的那个数） 43. result[1] = i; // 当前数的下标 44. return result; // 题目保证有解，找到后直接返回 45. } 46. } 47. // 理论上不会执行到这里（题目保证有解），返回结果数组（避免编译警告） 48. return result; 49. } 

需要注意的是HASH_FIND_INT的第二个参数需要传入查找的整型数据的指针，而HASH_ADD_INT的第二个参数传入需要添加节点的整型数据本身。