c语言给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
时间: 2023-11-16 20:53:40 浏览: 240
C语言第07章-一维数组和二维数组1完整.pptx
好的,这是一道经典的数组问题。我们可以使用暴力法、哈希表等多种方法来解决。
这里提供一个使用哈希表的解法,时间复杂度为 O(n):
1. 定义一个哈希表,用于存储数组中每个元素的值和它对应的下标。
2. 遍历数组,对于每个元素 nums[i],在哈希表中查找是否存在 target - nums[i] 的值。
3. 如果存在,则返回它们的下标;否则将 nums[i] 和 i 存入哈希表中,继续遍历。
代码如下:
```
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int hash[numsSize]; // 哈希表
memset(hash, -1, sizeof(hash)); // 初始化为-1
int* res = (int*)malloc(sizeof(int) * 2); // 存放结果
*returnSize = 2;
for (int i = 0; i < numsSize; i++) {
int complement = target - nums[i];
if (hash[complement] != -1) { // 找到了
res[0] = hash[complement];
res[1] = i;
return res;
}
hash[nums[i]] = i; // 没找到,存入哈希表
}
return res;
}
```
阅读全文