请用C语言编写程序解决问题:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。要求用哈希表实现。参考思路:一个简单的实现使用了两次迭代。在第一次迭代中,我们将每个元素的值和它的索引添加到表中。然后,在第二次迭代中,我们将检查每个元素所对应的目标元素(target - nums[i])是否存在于表中。注意,该目标元素不能是 nums[i]本身! 比如,给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 输入: 第一行: 数组nums 的元素个数 第二行:逐个、依次输入nums 数组元素 第三行:输入目标值 target 输出:按照从小到大顺序输出正确的数组下标值(不是数组元素)
时间: 2024-02-28 19:54:58 浏览: 66
c语言-leetcode题解之0081-search-in-rotated-sorted-array-ii.zip
以下是C语言的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int val;
int index;
struct Node *next;
} Node;
int main() {
int n, target;
scanf("%d", &n);
int *nums = (int*)malloc(sizeof(int) * n);
Node **hashTable = (Node**)calloc(10001, sizeof(Node*));
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
int idx = nums[i] % 10001;
Node *p = hashTable[idx];
if (p == NULL) {
hashTable[idx] = (Node*)malloc(sizeof(Node));
hashTable[idx]->val = nums[i];
hashTable[idx]->index = i;
hashTable[idx]->next = NULL;
} else {
while (p->next != NULL) {
p = p->next;
}
p->next = (Node*)malloc(sizeof(Node));
p->next->val = nums[i];
p->next->index = i;
p->next->next = NULL;
}
}
scanf("%d", &target);
for (int i = 0; i < n; i++) {
int idx = (target - nums[i]) % 10001;
Node *p = hashTable[idx];
while (p != NULL) {
if (p->val == target - nums[i] && p->index != i) {
printf("%d %d\n", i, p->index);
free(nums);
for (int j = 0; j < 10001; j++) {
Node *q = hashTable[j];
while (q != NULL) {
Node *tmp = q;
q = q->next;
free(tmp);
}
}
free(hashTable);
return 0;
}
p = p->next;
}
}
free(nums);
for (int i = 0; i < 10001; i++) {
Node *p = hashTable[i];
while (p != NULL) {
Node *tmp = p;
p = p->next;
free(tmp);
}
}
free(hashTable);
return 0;
}
```
该程序首先读入数组的元素个数和数组元素,然后使用哈希表将每个元素的值和索引添加到表中。接着读入目标值 target,并在哈希表中查找与数组中当前元素配对的元素。如果找到了,则输出它们的索引。最后释放内存并退出程序。
阅读全文