c - 找到序列中存在的两个整数 sum(a, b) = target

Question

任务是:

Input from file input.txt and output to file output.txt The first line is target number. The second line is sequence of positive integers in range 1 to 999999999.

If any two of these integers in sum equals to the target the program has to output 1 otherwise 0.

例子:

5
1 7 3 4 7 9

输出:1

这是我的程序。它通过了 5 次测试并失败了第 6 次 - 错误的结果。我需要帮助来找到错误或重写它。

#include <stdio.h>

int main() {
    FILE *fs = fopen("input.txt", "r");
    int target;
    fscanf(fs, "%d", &target);
    unsigned char bitset[1 + target / 8];

    int isFound = 0;

    for (int number; !isFound && fscanf(fs, "%d", &number) == 1;) {
        if (number <= target) {
            const int compliment = target - number;
            isFound = (bitset[compliment / 8] & (1 << (compliment % 8))) > 0;
            bitset[number / 8] |= 1 << (number % 8);
        }
    }
    fclose(fs);

    fs = fopen("output.txt", "w");
    fprintf(fs,"%d", isFound);
    fclose(fs);

    return 0;
}

Answer 1

在您的代码中，您忘记清除本地数组，因此您会得到未定义的行为和不正确的结果。请注意，可变大小的数组无法使用初始化程序进行初始化，因此您应该使用 memset 来清除此数组。

此方法的问题是 target 可能非常大，最大可达 1999999997，这使得通过自动存储定义必要大小的位数组变得不切实际。您应该使用 calloc() 分配此数组，以便将其初始化为 0。

修改后的版本:

#include <limits.h>
#include <stdio.h>

int main() {
    FILE *fs = fopen("input.txt", "r");
    unsigned long target, number;  /* type long has at least 32 bits */
    int isFound = 0;

    if (!fs || fscanf(fs, "%lu", &target) != 1)
        return 1;

    if (target <= 1999999998 && target / 8 < SIZE_MAX) {
        unsigned char *bitset = calloc(1, 1 + target / 8);
        if (bitset != NULL) {
            while (!isFound && fscanf(fs, "%lu", &number) == 1) {
                if (number <= target) {
                    unsigned long complement = target - number;
                    isFound = (bitset[complement / 8] >> (complement % 8)) & 1;
                    bitset[number / 8] |= 1 << (number % 8);
                }
            }
            free(bitset);
        }
    }
    fclose(fs);

    fs = fopen("output.txt", "w");
    fprintf(fs, "%d", isFound);
    fclose(fs);

    return 0;
}

对于非常大的 target 值，可以使用不同的方法，使用哈希表:

• 读取下一个值number
• 如果target-number在哈希表中，found=1，停止
• 如果不是，将数字存入哈希表
• 继续