C语言数据结构与算法

Question

给出若干个整数，询问其中是否有一对数的和等于给定数，C语言数据结构与算法

Answer 1

引自免费微信小程序：皆我百晓生

要解决这个问题，我们可以使用哈希表（也可以称为字典或映射）来存储已经遍历过的数字及其索引。这样我们可以在常数时间内检查一个数字的互补数是否存在。以下是完整的C语言代码实现：

#include <stdio.h>
#include <stdbool.h>

int main() {
    int n;
    scanf("%d", &n);

    int nums[n];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &nums[i]);
    }

    int m;
    scanf("%d", &m);

    // 创建一个哈希表
    bool hash[100000001] = {false}; // 哈希表大小应足够大，至少能容纳所有可能的和
    int complement_index = -1;

    for (int i = 0; i < n; ++i) {
        int target = m - nums[i]; // 计算目标值
        if (hash[target]) { // 如果目标值已经在哈希表中
            printf("%d %d\n", nums[hash[target]], nums[i]); // 输出这对数并退出循环
            return 0;
        }
        hash[nums[i]] = true; // 将当前数添加到哈希表
    }

    printf("No\n"); // 没有找到符合条件的数对

    return 0;
}

这段代码首先读取输入的整数数量n、数组中的每个整数以及所需的和m。然后，它创建一个大小为100000001的布尔数组作为哈希表，用于存储已遍历过的数字。接着，程序遍历整个数组，对于每个元素，计算其与m的差值，并检查这个差值是否在哈希表中。如果找到了，就输出这对数并结束程序。如果没有找到，则将当前元素添加到哈希表中。如果遍历结束后仍未找到合适的数对，程序会输出"No"。

注意：这个代码假设输入的整数范围不会超过10^8，且数组中的数字是升序排列的。如果这些假设不成立，你需要进行相应的调整，例如使用排序算法处理无序数组，或者增大哈希表的大小以适应更大的整数范围。