使用C语言编写程序给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。输入整数N
时间: 2024-09-13 20:02:05 浏览: 68
在C语言中,可以通过创建一个哈希表来存储遍历数组时的元素值和对应的索引,以实现快速查找和为为目标值的两个整数。下面是一种可能的实现方法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义哈希表节点结构体
typedef struct HashNode {
int key;
int value;
struct HashNode *next;
} HashNode;
// 定义哈希表结构体
typedef struct {
HashNode **buckets;
int size;
} HashTable;
// 创建哈希表
HashTable* createHashTable(int size) {
HashTable *hashTable = (HashTable*)malloc(sizeof(HashTable));
hashTable->size = size;
hashTable->buckets = (HashNode**)malloc(sizeof(HashNode*) * size);
for (int i = 0; i < size; i++) {
hashTable->buckets[i] = NULL;
}
return hashTable;
}
// 释放哈希表内存
void freeHashTable(HashTable *hashTable) {
for (int i = 0; i < hashTable->size; i++) {
HashNode *node = hashTable->buckets[i];
while (node) {
HashNode *temp = node;
node = node->next;
free(temp);
}
}
free(hashTable->buckets);
free(hashTable);
}
// 插入键值对到哈希表
void insert(HashTable *hashTable, int key, int value) {
int index = key % hashTable->size;
HashNode *newNode = (HashNode*)malloc(sizeof(HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = hashTable->buckets[index];
hashTable->buckets[index] = newNode;
}
// 在哈希表中查找键对应的值
int search(HashTable *hashTable, int key) {
int index = key % hashTable->size;
HashNode *node = hashTable->buckets[index];
while (node) {
if (node->key == key) {
return node->value;
}
node = node->next;
}
return -1; // 未找到
}
// 返回数组中两个整数的和为target的下标
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
HashTable *hashTable = createHashTable(numsSize);
int *result = (int*)malloc(sizeof(int) * 2);
for (int i = 0; i < numsSize; ++i) {
int complement = target - nums[i];
int complementIndex = search(hashTable, complement);
if (complementIndex != -1) {
result[0] = complementIndex;
result[1] = i;
*returnSize = 2;
freeHashTable(hashTable);
return result;
}
insert(hashTable, nums[i], i);
}
*returnSize = 0;
freeHashTable(hashTable);
return result;
}
int main() {
int nums[] = {2, 7, 11, 15};
int target = 9;
int returnSize = 0;
int* indices = twoSum(nums, sizeof(nums) / sizeof(nums[0]), target, &returnSize);
if (returnSize == 2) {
printf("找到的两个数的下标为: [%d, %d]\n", indices[0], indices[1]);
} else {
printf("未找到符合条件的两个数\n");
}
free(indices);
return 0;
}
```
这段代码定义了一个哈希表,并提供了创建、插入和查找的功能。`twoSum`函数利用这个哈希表来快速查找是否存在和为`target`的两个整数。如果找到,返回它们的下标;否则,返回没有找到的信息。
阅读全文
相关推荐
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)