给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案c语言
时间: 2024-10-28 21:12:03 浏览: 10
两数之和 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个
给定一个整数数组 `nums` 和一个目标值 `target`,你需要找到数组中存在的一对整数,它们的和等于 `target`。这个问题通常被称为“两数之和”(Two Sum)。这个经典的查找问题可以使用哈希表(C语言中称为关联数组或者 map)来解决,步骤如下:
1. 遍历整个数组 `nums`,对于每个元素 `num`:
a. 查看目标值 `target - num` 是否已经在哈希表中。如果找到了,说明已经找到了一对和为目标值的数,直接返回这两个数的索引(当前元素的索引和哈希表中对应数值的索引)。
2. 如果 `target - num` 没有在哈希表中,将当前元素及其索引添加到哈希表中,以便后续查找。
这里是一个简单的C语言函数实现示例:
```c
#include <stdio.h>
#include <stdlib.h>
int* twoSum(int* nums, int numsSize, int target) {
if (nums == NULL || numsSize <= 0) return NULL;
// 创建一个大小为target+1的哈希表,用于存储元素和对应的索引
int* hashTable = malloc((target + 1) * sizeof(int));
for (int i = 0; i <= target; ++i) {
hashTable[i] = -1;
}
// 遍历数组
for (int i = 0; i < numsSize; ++i) {
int complement = target - nums[i];
if (hashTable[complement] != -1) {
// 找到了解,返回结果
return &hashTable[complement], &nums[i];
}
hashTable[nums[i]] = i;
}
free(hashTable);
return NULL;
}
// 示例
int main() {
int nums[] = {2, 7, 11, 15};
int target = 9;
int* result = twoSum(nums, sizeof(nums) / sizeof(nums[0]), target);
if (result != NULL) {
printf("Solution found at indices %d and %d\n", result[0], result[1]);
} else {
printf("No solution found.\n");
}
return 0;
}
```
阅读全文