给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。用c语言
时间: 2024-10-12 20:03:39 浏览: 30
两数之和 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个
这个问题描述的是寻找数组中两个特定元素的和等于给定目标值的解决方案,通常被称为“两数之和”(Two Sum)。这是一个常见的算法问题,可以使用哈希表(HashMap 或 unordered_map)来解决。以下是使用 C 语言的一个简单解决方案:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义结构体来存储元素和它的索引
typedef struct {
int val;
int index;
} Pair;
// 查找函数,如果找到符合条件的元素,则返回其索引
int findSum(int *nums, int n, int target) {
// 创建一个空的哈希表
Pair* hashTable = malloc(n * sizeof(Pair));
for (int i = 0; i < n; i++) {
hashTable[i].val = nums[i];
hashTable[i].index = i;
}
// 遍历数组
for (int i = 0; i < n - 1; i++) {
int complement = target - nums[i];
// 如果找到了互补元素,返回它们的索引
if (complement != nums[i] && findInHash(hashTable, complement, i + 1, n)) {
return {i, hashTable[findInHash(hashTable, complement, i + 1, n)].index};
}
}
// 如果找不到解,释放内存并返回 -1
free(hashTable);
return -1;
}
// 内部辅助函数,查找目标值在哈希表中的位置
int findInHash(Pair* hashTable, int target, int start, int end) {
for (int i = start; i < end; i++) {
if (hashTable[i].val == target) {
return i;
}
}
return -1;
}
int main() {
int nums[] = {2, 7, 11, 15};
int n = sizeof(nums) / sizeof(nums[0]);
int target = 9;
int result[] = findSum(nums, n, target);
if (result[0] != -1) {
printf("The two numbers with sum %d are at indices %d and %d.\n", target, result[0], result[1]);
} else {
printf("No pair found with sum %d.\n", target);
}
return 0;
}
```
这个程序首先创建了一个哈希表,然后通过一次遍历来查找是否存在目标值的补数。如果找到了,就直接返回这两个数的索引;如果没有找到,返回 -1 表示无解。
阅读全文