莆田社交网站免费行情网站大全搜狐网

莆田社交网站,免费行情网站大全搜狐网,南宁比优建站,做碳循环的网站一、题目描述给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那两个整数#xff0c;并返回它们的数组下标。你可以假设每种输入 只会对应一个答案#xff0c;并且 同一个元素不能使用两次。可以按任意顺序返回答案。示例…一、题目描述给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值 target 的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案并且同一个元素不能使用两次。可以按任意顺序返回答案。示例 1输入: nums [2,7,11,15], target 9 输出: [0,1] 解释: nums[0] nums[1] 9示例 2输入: nums [3,2,4], target 6 输出: [1,2]示例 3输入: nums [3,3], target 6 输出: [0,1]提示2 ≤ nums.length ≤ 10⁴-10⁹ ≤ nums[i] ≤ 10⁹-10⁹ ≤ target ≤ 10⁹只会存在一个有效答案二、解题思路这道题是LeetCode 最经典的哈希表题目之一也是很多面试的入门题。常见解法有两种1️⃣ 暴力枚举2️⃣ 哈希表优化推荐三、方法一暴力枚举思路最直接的方法就是两层循环枚举所有组合第一个循环选择第一个数nums[i]第二个循环选择第二个数nums[j]判断nums[i] nums[j] target如果成立则返回两个下标。动图思路假设数组[2,7,11,15]target 9枚举过程2 7 9 ✔返回[0,1]C语言代码#include stdlib.h int* twoSum(int* nums, int numsSize, int target, int* returnSize) { int* res (int*)malloc(sizeof(int) * 2); for(int i 0; i numsSize; i) { for(int j i 1; j numsSize; j) { if(nums[i] nums[j] target) { res[0] i; res[1] j; *returnSize 2; return res; } } } *returnSize 0; return NULL; }复杂度分析复杂度数值时间复杂度O(n²)空间复杂度O(1)当数组较大时效率会明显下降。四、方法二哈希表推荐⭐核心思想如果a b target那么b target - a遍历数组时计算当前数需要的补数complement target - nums[i]查询哈希表中是否存在该补数如果存在 → 找到答案如果不存在 → 将当前数字存入哈希表这样只需要遍历一次数组。执行过程示例数组[2,7,11,15]target 9遍历过程inums[i]补数哈希表027存入2172找到2 ✔返回[0,1]五、C语言实现哈希表由于 C 语言没有内置哈希表我们可以用链地址法实现简单哈希表。#include stdlib.h #define SIZE 20011 typedef struct Node { int key; int value; struct Node* next; }Node; Node* hashTable[SIZE]; int hash(int key) { if(key 0) key -key; return key % SIZE; } void insert(int key, int value) { int h hash(key); Node* node (Node*)malloc(sizeof(Node)); node-key key; node-value value; node-next hashTable[h]; hashTable[h] node; } int find(int key) { int h hash(key); Node* cur hashTable[h]; while(cur) { if(cur-key key) return cur-value; cur cur-next; } return -1; } int* twoSum(int* nums, int numsSize, int target, int* returnSize) { for(int i 0; i SIZE; i) hashTable[i] NULL; int* res (int*)malloc(sizeof(int) * 2); for(int i 0; i numsSize; i) { int complement target - nums[i]; int index find(complement); if(index ! -1) { res[0] index; res[1] i; *returnSize 2; return res; } insert(nums[i], i); } *returnSize 0; return NULL; }六、复杂度分析复杂度数值时间复杂度O(n)空间复杂度O(n)因为只遍历了一次数组所以效率非常高。七、总结方法时间复杂度空间复杂度暴力枚举O(n²)O(1)哈希表O(n)O(n)在实际面试中哈希表解法是最推荐的方案。核心思想可以总结为一句话在遍历数组时利用哈希表快速查找当前数字所需要的补数。八、延伸题目Two Sum 是很多题目的基础例如三数之和Three Sum四数之和Four Sum两数之和 II有序数组掌握 Two Sum 的哈希表思想可以帮助解决很多类似问题。如果这篇文章对你有帮助欢迎点赞 收藏 关注⭐后续会持续更新LeetCode 面试经典 150 题 C 语言题解专栏。