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-01 17:16:30 浏览: 59
以下是用哈希表实现的 C 代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 1000000
typedef struct {
int key;
int val;
struct hash_node *next;
} hash_node;
hash_node *hash_table[HASH_SIZE];
int hash(int key) {
return abs(key) % HASH_SIZE;
}
void insert(int key, int val) {
int h = hash(key);
hash_node *p = hash_table[h];
while (p != NULL) {
if (p->key == key) {
p->val = val;
return;
}
p = p->next;
}
p = (hash_node *)malloc(sizeof(hash_node));
p->key = key;
p->val = val;
p->next = hash_table[h];
hash_table[h] = p;
}
int find(int key) {
int h = hash(key);
hash_node *p = hash_table[h];
while (p != NULL) {
if (p->key == key) {
return p->val;
}
p = p->next;
}
return -1;
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
int *result = (int *)malloc(2 * sizeof(int));
*returnSize = 2;
for (int i = 0; i < numsSize; i++) {
insert(nums[i], i);
}
for (int i = 0; i < numsSize; i++) {
int j = find(target - nums[i]);
if (j != -1 && j != i) {
result[0] = i;
result[1] = j;
break;
}
}
return result;
}
int main() {
int n, target, *nums, *result, returnSize;
scanf("%d", &n);
nums = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &nums[i]);
}
scanf("%d", &target);
result = twoSum(nums, n, target, &returnSize);
printf("%d %d\n", result[0], result[1]);
free(nums);
free(result);
return 0;
}
```
输入格式为:
```
4
2 7 11 15
9
```
输出格式为:
```
0 1
```
其中,`0` 和 `1` 分别是下标,对应的元素是 `2` 和 `7`。
阅读全文