不使用指针给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。
时间: 2024-10-21 22:15:06 浏览: 27
在排序数组中查找元素的第一个和最后一个位置1
在C语言中,要找到一个整数数组`nums`中两个数相加等于`target`的两个下标,但不使用指针,可以使用哈希表(或称为关联数组)来存储每个元素及其出现的下标。这样,我们可以在常数时间内查找是否存在配对。
以下是一个简单的解决方案:
```c
#include <stdio.h>
#include <stdbool.h>
typedef struct {
int val;
int index;
} Pair;
// 使用结构体来表示数组元素及其下标
Pair findSum(int nums[], int target, int size) {
// 创建一个空的哈希表
int hash[5001] = {0}; // 假设我们的数组范围不超过10000
// 遍历数组,对于每个元素,检查哈希表中是否存在(target - nums[i])
for (int i = 0; i < size; ++i) {
if (hash[target - nums[i]] != 0) {
return (Pair){nums[i], hash[target - nums[i]]};
}
hash[nums[i]] = i; // 如果不存在,就将当前元素和其下标存入哈希表
}
// 没有找到匹配,返回空的Pair
return (Pair){-1, -1};
}
int main() {
int nums[] = {2, 7, 11, 15};
int target = 9;
int size = sizeof(nums) / sizeof(nums[0]);
Pair pair = findSum(nums, target, size);
if (pair.val == -1 && pair.index == -1) {
printf("No pair found.\n");
} else {
printf("Pair found at indices %d and %d with sum %d.\n", pair.index, pair.val, target);
}
return 0;
}
```
在这个代码中,我们首先创建了一个大小为`target + 1`的哈希表,然后遍历数组,如果找到了目标差值对应的元素,我们就找到了匹配的两个数。如果没有找到,我们就在哈希表中添加当前元素及其下标。
注意:这个方法的时间复杂度是O(n),其中n是数组的长度,因为我们只遍历了一次数组。空间复杂度也是O(n),因为最坏情况下可能需要存储所有的元素。
阅读全文