给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。 你可以按任意顺序返回答案 用C语言
时间: 2024-08-24 20:01:12 浏览: 124
这是一个经典的双指针问题,通常可以使用哈希表或者排序算法来解决。这里提供一种使用哈希表的解法,步骤如下:
1. 创建一个空的哈希表(可以用 C 语言里的 `struct` 或者 `unordered_map` 实现)用于存储数组中每个元素及其索引。
2. 遍历数组 `nums`,对于每个元素 `num`:
- 如果哈希表中存在 `target - num`,说明我们已经找到了一对和为目标值的数。此时,返回当前 `num` 的索引和哈希表中找到的 `target - num` 对应的索引。
- 否则,将 `num` 添加到哈希表中,作为键,它的索引作为值。
如果遍历完整个数组都没有找到合适的配对,那么就表示不存在这样的两个数。以下是用 C 语言实现的一个简化版伪代码:
```c
#include <stdio.h>
#include <stdbool.h>
// 假设哈希表使用链表实现
typedef struct Node {
int value;
int index;
struct Node* next;
} ListNode;
ListNode* createHashMap(int target, int* nums, int size) {
ListNode* hashTable = NULL;
for (int i = 0; i < size; ++i) {
if (hashTable == NULL || nums[i] != hashTable->value) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->value = nums[i];
newNode->index = i;
newNode->next = hashTable;
hashTable = newNode;
} else {
printf("Found a duplicate number %d at index %d\n", nums[i], i);
return NULL; // 如果有重复,直接返回错误
}
}
return hashTable;
}
void findTwoSum(int* nums, int size, int target, int* result) {
ListNode* hashTable = createHashMap(target, nums, size);
if (hashTable != NULL) {
ListNode* current = hashTable;
while (current != NULL) {
int complementIndex = current->index;
int complementValue = target - current->value;
if (hashTable->next != NULL && hashTable->next->value == complementValue) {
*result = {complementIndex, current->index};
break;
}
current = current->next;
}
}
}
int main() {
int nums[] = {2, 7, 11, 15};
int target = 9;
int result[2];
findTwoSum(nums, sizeof(nums) / sizeof(nums[0]), target, result);
printf("Indices of the two numbers that sum to %d are: %d and %d\n", target, result[0], result[1]);
return 0;
}
```
注意这只是一个基本版本的解决方案,实际应用中可能会根据具体需求优化数据结构或者算法。如果你需要详细解释代码的工作原理或者其他相关问题,请告诉我,我会继续帮助你。
阅读全文