题目

攻克点

  1. 如何确定数组中两数相加的和是否存在于这个数组中
  2. 如何求出遍历循环的范围
  3. 由说明可知，两组数若相加起来答案相同，只记一次，需要一个方法去重
  4. 如何计数

原理

确定数组中两数相加的和是否存在于这个数组中

  • 建立一个数组，用for循环输入所需数据
  • 再建立一个布尔型数组，利用数组嵌套，使这个数组中该数数值与其位置相绑定，例如a[5]=3,定义g[a[5]]=1,即表示g[3]=1,即数组中存在3这个数字
  • 核心就是用数组的个数来代表其数值

求出遍历循环的范围

  • 求所有可能的两个数相加的结果出现的次数，而这个结果的范围是从最小的两数之和到最大的两数之和
  • 所以只需要求出最大值即可，循环范围小于最大值

求和并去重

  • 再定义一个数组，计算数组中两数相加，即利用循环计算a[i] + a[j]，然后利用数组嵌套，如t[a[i] + a[j]]，每计算一次，将其结果+1
  • 例如a[1]=3, a[2]=4,t[a[1]+a[2]]=t[7] ，t[7]++
  • a[3]=4,a[2]=4, t[a[1]+a[2]]=t[7]，t[7]++
  • 定义数组中初始都为0，两个数相加结果为x，则t[x]必>=1

如何计数

  • 由上可知，只需t[i] > 0 && g[i]==1，即表示其和存在，定义变量，遍历数组t，每符合一次上述情况，结果加一
  • 在t[i]中的i，只会出现一次，且重复的次数会在t[i]的值中体现，所以能达到去重的效果

代码分析

  1. 确定数组中两数相加的和是否存在于这个数组中，利用循环和数组嵌套

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

    即如果g[x]=1，则x存在于原数组a中

  2. 定义maxn，利用循环遍历找出两数相加的最大值

    maxn = 0;                // 初始化 maxn
    for (int i = 1; i < n; i++)
    { // 暴力枚举求出可以加出的数
        for (int j = i + 1; j <= n; j++)
        {
            if (a[i] + a[j] > maxn)
            {
                maxn = a[i] + a[j]; // 求出数中最大值
            }
        }
    }

  3. 建立数组t，存储a[i] + a[j]值出现的次数

    for (int i = 1; i < n; i++)
    { // 暴力枚举求出可以加出的数
        for (int j = i + 1; j <= n; j++)
        {
            t[a[i] + a[j]]++; // a[i]+a[j]这个数被加出来了
        }
    }

  4. 定义变量，用来存储重复的次数

    ans = 0; // 初始化 ans
    for (int i = 1; i <= maxn; i++)
    { // 只需要枚举到最大值即可
        if (t[i] > 0 && g[i])
            ans++; // 判断是否满足，满足就 ans++
    }

  5. 打印结果

    printf("%d\n", ans);

完整代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const int M = 20005;      // 20005由于最大值是10000+10000=20000，const int是静态定义，定义后该值（即M)无法修改。
int t[M], g[M];           // t是桶，t[i]表示值为i的数在集合中两两相加出现了几次，g[i]表示值为i的数是否在原集合中，1为在，0为不在
int n, a[105], ans, maxn; // a数组开105是由于总共最多100个数

int main()
{
    scanf("%d", &n);
    memset(g, 0, sizeof(g)); // 初始化 g 数组
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]); // 读入
        g[a[i]] = 1;        // 在集合中赋值为1
    }

    memset(t, 0, sizeof(t)); // 初始化 t 数组
    maxn = 0;                // 初始化 maxn
    for (int i = 1; i < n; i++)
    { // 暴力枚举求出可以加出的数
        for (int j = i + 1; j <= n; j++)
        {
            t[a[i] + a[j]]++; // a[i]+a[j]这个数被加出来了
            if (a[i] + a[j] > maxn)
            {
                maxn = a[i] + a[j]; // 求出数中最大值
            }
        }
    }

    ans = 0; // 初始化 ans
    for (int i = 1; i <= maxn; i++)
    { // 只需要枚举到最大值即可
        if (t[i] > 0 && g[i])
            ans++; // 判断是否满足，满足就 ans++
    }

    printf("%d\n", ans);
    return 0;
}
最后修改：2025 年 07 月 18 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏