题目描述1. 两数之和给定一个整数数组nums和一个目标值target需要在数组中找出两个数使它们的和等于target并返回这两个数的下标。假设每个输入只对应一个答案且不能重复使用同一个元素。答案顺序不限。方法总结1.暴力枚举法核心思路用双重循环遍历数组外层循环固定一个数内层循环检查后续数是否满足和等于target。优点简单易懂适合初学者。缺点时间复杂度高为 O(n^2)数据量大时效率低。C代码关键使用malloc分配内存存储结果双重循环避免重复检查。2.哈希表法核心思路用哈希表记录已遍历的值和下标。对每个数计算complement target - nums[i]检查complement是否在哈希表中。如果找到返回下标否则将当前数存入表。优点高效时间复杂度降至 O(n)适合大规模数据。缺点需要额外空间存储哈希表。C代码关键使用UT_hash库实现哈希表操作定义结构体、查找和添加。核心讲解1.暴力枚举法1. 1核心思路就像在班里找两个同学他们的体重加起来刚好等于目标体重。我们让每个同学都去问他后面的每一个同学“咱俩加起来是 target 不”一旦找到就把他俩的座位号数组下标返回。1.2C语言代码#include stdio.h #include stdlib.h // 函数返回两个下标需要用 malloc 分配内存 int* twoSum(int* nums, int numsSize, int target, int* returnSize) { // 1. 先分配能存2个整数的内存因为要返回两个下标 int* result (int*)malloc(2 * sizeof(int)); *returnSize 2; // 告诉调用者我们返回了2个元素 // 2. 双重循环第一个人从第0个开始 for (int i 0; i numsSize; i) { // 3. 第二个人从第一个人的后面开始避免重复问 for (int j i 1; j numsSize; j) { // 4. 检查如果 nums[i] nums[j] 等于 target if (nums[i] nums[j] target) { result[0] i; // 存第一个下标 result[1] j; // 存第二个下标 return result; // 找到就直接跑不用再找了 } } } // 题目说一定有答案所以这里不会走到但为了代码规范写个返回 return result; } // 测试用的 main 函数 int main() { int nums[] {2, 7, 11, 15}; int target 9; int returnSize; int* res twoSum(nums, 4, target, returnSize); printf(结果[%d, %d]\n, res[0], res[1]); // 输出 [0, 1] free(res); // 记得释放 malloc 的内存 return 0; }1.3逐块拆解int* result (int*)malloc(2 * sizeof(int));我们要返回两个下标所以得在内存里 “租” 一块能放 2 个整数的地方。malloc就是租内存的函数用完记得free还回去。for (int i 0; i numsSize; i)这是外层循环i是第一个人的座位号从第 0 排开始一直走到最后。for (int j i 1; j numsSize; j)这是内层循环j是第二个人的座位号必须从i1开始不然会出现 “自己问自己” 或者 “重复问” 的情况比如先问 0 和 1又问 1 和 0。if (nums[i] nums[j] target)核心判断看看这两个人的 “体重”数组里的值加起来是不是刚好等于目标。2. 哈希表法2. 1核心思路这回我们不挨个问了而是拿个小本子哈希表记录已经见过的人每遇到一个新同学先算一下“我需要找一个体重是target - 当前体重的人”然后翻小本子看看这个人来过没如果来过直接把他的座位号和当前座位号返回如果没来过把当前同学的体重和座位号记在小本子上继续往后走。这样只需要走一遍数组时间复杂度直接降到O(n)1.2C语言代码#include stdio.h #include stdlib.h #include uthash.h // 引入 UT_hash 头文件 // 1. 定义哈希表的结构体就像定义小本子的每一页 typedef struct { int key; // 存数组里的值体重 int val; // 存对应的下标座位号 UT_hash_handle hh; // 这是 UT_hash 要求的固定写法不用管它 } HashTable; int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* result (int*)malloc(2 * sizeof(int)); *returnSize 2; HashTable* hashTable NULL; // 初始化哈希表为空小本子是空的 for (int i 0; i numsSize; i) { // 2. 算一下我要找的数是啥 int complement target - nums[i]; HashTable* tmp; // 3. 去小本子里找有没有 complement 这个 key HASH_FIND_INT(hashTable, complement, tmp); if (tmp ! NULL) { // 4. 找到了直接返回结果 result[0] tmp-val; // 小本子里存的下标 result[1] i; // 当前的下标 return result; } else { // 5. 没找到把当前的数和下标存进小本子 tmp (HashTable*)malloc(sizeof(HashTable)); tmp-key nums[i]; tmp-val i; HASH_ADD_INT(hashTable, key, tmp); // 往哈希表里加 } } return result; } // 测试用的 main 函数 int main() { int nums[] {3, 2, 4}; int target 6; int returnSize; int* res twoSum(nums, 3, target, returnSize); printf(结果[%d, %d]\n, res[0], res[1]); // 输出 [1, 2] free(res); return 0; }1.3UT_hash讲解定义结构体HashTable就像小本子的一页key是记的内容val是备注hh是固定格式。HASH_FIND_INT翻小本子找东西。HASH_ADD_INT往小本子里写东西。类似题目练习巩固哈希表法现在我来出一道类似题目帮你巩固哈希表法给定数组[1, 3, 5, 7]目标值target 8。请找出两个数之和为8的下标索引从0开始。提示使用哈希表法实现先计算complement再查表或存储。答案只有一个结果正确下标为[1, 2]因为3 5 8。
【迈好编程第一步】leetcode01.两数之和
题目描述1. 两数之和给定一个整数数组nums和一个目标值target需要在数组中找出两个数使它们的和等于target并返回这两个数的下标。假设每个输入只对应一个答案且不能重复使用同一个元素。答案顺序不限。方法总结1.暴力枚举法核心思路用双重循环遍历数组外层循环固定一个数内层循环检查后续数是否满足和等于target。优点简单易懂适合初学者。缺点时间复杂度高为 O(n^2)数据量大时效率低。C代码关键使用malloc分配内存存储结果双重循环避免重复检查。2.哈希表法核心思路用哈希表记录已遍历的值和下标。对每个数计算complement target - nums[i]检查complement是否在哈希表中。如果找到返回下标否则将当前数存入表。优点高效时间复杂度降至 O(n)适合大规模数据。缺点需要额外空间存储哈希表。C代码关键使用UT_hash库实现哈希表操作定义结构体、查找和添加。核心讲解1.暴力枚举法1. 1核心思路就像在班里找两个同学他们的体重加起来刚好等于目标体重。我们让每个同学都去问他后面的每一个同学“咱俩加起来是 target 不”一旦找到就把他俩的座位号数组下标返回。1.2C语言代码#include stdio.h #include stdlib.h // 函数返回两个下标需要用 malloc 分配内存 int* twoSum(int* nums, int numsSize, int target, int* returnSize) { // 1. 先分配能存2个整数的内存因为要返回两个下标 int* result (int*)malloc(2 * sizeof(int)); *returnSize 2; // 告诉调用者我们返回了2个元素 // 2. 双重循环第一个人从第0个开始 for (int i 0; i numsSize; i) { // 3. 第二个人从第一个人的后面开始避免重复问 for (int j i 1; j numsSize; j) { // 4. 检查如果 nums[i] nums[j] 等于 target if (nums[i] nums[j] target) { result[0] i; // 存第一个下标 result[1] j; // 存第二个下标 return result; // 找到就直接跑不用再找了 } } } // 题目说一定有答案所以这里不会走到但为了代码规范写个返回 return result; } // 测试用的 main 函数 int main() { int nums[] {2, 7, 11, 15}; int target 9; int returnSize; int* res twoSum(nums, 4, target, returnSize); printf(结果[%d, %d]\n, res[0], res[1]); // 输出 [0, 1] free(res); // 记得释放 malloc 的内存 return 0; }1.3逐块拆解int* result (int*)malloc(2 * sizeof(int));我们要返回两个下标所以得在内存里 “租” 一块能放 2 个整数的地方。malloc就是租内存的函数用完记得free还回去。for (int i 0; i numsSize; i)这是外层循环i是第一个人的座位号从第 0 排开始一直走到最后。for (int j i 1; j numsSize; j)这是内层循环j是第二个人的座位号必须从i1开始不然会出现 “自己问自己” 或者 “重复问” 的情况比如先问 0 和 1又问 1 和 0。if (nums[i] nums[j] target)核心判断看看这两个人的 “体重”数组里的值加起来是不是刚好等于目标。2. 哈希表法2. 1核心思路这回我们不挨个问了而是拿个小本子哈希表记录已经见过的人每遇到一个新同学先算一下“我需要找一个体重是target - 当前体重的人”然后翻小本子看看这个人来过没如果来过直接把他的座位号和当前座位号返回如果没来过把当前同学的体重和座位号记在小本子上继续往后走。这样只需要走一遍数组时间复杂度直接降到O(n)1.2C语言代码#include stdio.h #include stdlib.h #include uthash.h // 引入 UT_hash 头文件 // 1. 定义哈希表的结构体就像定义小本子的每一页 typedef struct { int key; // 存数组里的值体重 int val; // 存对应的下标座位号 UT_hash_handle hh; // 这是 UT_hash 要求的固定写法不用管它 } HashTable; int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* result (int*)malloc(2 * sizeof(int)); *returnSize 2; HashTable* hashTable NULL; // 初始化哈希表为空小本子是空的 for (int i 0; i numsSize; i) { // 2. 算一下我要找的数是啥 int complement target - nums[i]; HashTable* tmp; // 3. 去小本子里找有没有 complement 这个 key HASH_FIND_INT(hashTable, complement, tmp); if (tmp ! NULL) { // 4. 找到了直接返回结果 result[0] tmp-val; // 小本子里存的下标 result[1] i; // 当前的下标 return result; } else { // 5. 没找到把当前的数和下标存进小本子 tmp (HashTable*)malloc(sizeof(HashTable)); tmp-key nums[i]; tmp-val i; HASH_ADD_INT(hashTable, key, tmp); // 往哈希表里加 } } return result; } // 测试用的 main 函数 int main() { int nums[] {3, 2, 4}; int target 6; int returnSize; int* res twoSum(nums, 3, target, returnSize); printf(结果[%d, %d]\n, res[0], res[1]); // 输出 [1, 2] free(res); return 0; }1.3UT_hash讲解定义结构体HashTable就像小本子的一页key是记的内容val是备注hh是固定格式。HASH_FIND_INT翻小本子找东西。HASH_ADD_INT往小本子里写东西。类似题目练习巩固哈希表法现在我来出一道类似题目帮你巩固哈希表法给定数组[1, 3, 5, 7]目标值target 8。请找出两个数之和为8的下标索引从0开始。提示使用哈希表法实现先计算complement再查表或存储。答案只有一个结果正确下标为[1, 2]因为3 5 8。
