有一个整数序列,设计一个算法判断其中是否存在两个元素的和恰好等于给定的整数k,输出示例C语言代码
时间: 2024-05-09 18:22:11 浏览: 11
可以使用哈希表来解决这个问题。首先将整数序列中的每个元素存储到哈希表中,然后遍历整个序列,对于每个元素i,查找哈希表中是否存在k-i。如果找到了,就说明存在两个元素的和恰好等于给定的整数k,否则就不存在。代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 1000001 // 哈希表大小
struct node {
int key;
int val;
struct node* next;
};
struct hash_table {
struct node** table;
int size;
};
// 创建哈希表
struct hash_table* create_table(int size) {
struct hash_table* htable = (struct hash_table*) malloc(sizeof(struct hash_table));
htable->table = (struct node**) malloc(sizeof(struct node*) * size);
htable->size = size;
// 初始化哈希表
for (int i = 0; i < size; i++) {
htable->table[i] = NULL;
}
return htable;
}
// 哈希函数,使用取模运算
int hash(int key, int size) {
return abs(key % size);
}
// 查找key在哈希表中的位置
struct node* lookup(struct hash_table* htable, int key) {
int pos = hash(key, htable->size);
struct node* cur = htable->table[pos];
while (cur != NULL && cur->key != key) {
cur = cur->next;
}
return cur;
}
// 添加key-value对到哈希表中
void add(struct hash_table* htable, int key, int val) {
int pos = hash(key, htable->size);
struct node* cur = htable->table[pos];
while (cur != NULL && cur->key != key) {
cur = cur->next;
}
if (cur == NULL) {
cur = (struct node*) malloc(sizeof(struct node));
cur->key = key;
cur->val = val;
cur->next = htable->table[pos];
htable->table[pos] = cur;
}
}
// 判断整数序列中是否存在两个元素的和恰好等于给定的整数k
int has_sum(int* nums, int n, int k) {
struct hash_table* htable = create_table(TABLE_SIZE);
for (int i = 0; i < n; i++) {
add(htable, nums[i], nums[i]); // 值和键都是nums[i]
}
for (int i = 0; i < n; i++) {
int complement = k - nums[i];
struct node* node = lookup(htable, complement);
if (node != NULL && node->val != nums[i]) {
return 1; // 存在两个元素的和恰好等于k
}
}
return 0; // 不存在
}
// 测试程序
int main() {
int nums[] = {1, 2, 3, 4, 5};
int n = sizeof(nums) / sizeof(int);
int k = 7;
if (has_sum(nums, n, k)) {
printf("存在两个元素的和恰好等于%d\n", k);
} else {
printf("不存在两个元素的和恰好等于%d\n", k);
}
return 0;
}
```
当输入整数序列为{1, 2, 3, 4, 5},给定整数k为7时,上述程序输出“存在两个元素的和恰好等于7”。