637.可表示的数 题解

题目描述

有N个整数从左到右排成一行，如果某个数等于它前面的2个数的和，就称这个数是可以表示的数。问给定的数列里有多少个数是可以表示的数。

输入格式

第一行1个整数N，表示数列有多少个整数。1<=N<=10000。

第二行N个正整数，每个正整数不超过10000。

输出格式

一个整数，有多少可表示的数。

题意分析

本题让我们输入一个数组，遍历数组，在0到i - 1的范围里查找2个数，与a[i]相等

解题思路

错误思路❌

用三循环，依次遍历数组，如果在0到i - 1的范围内有符合条件的数时，答案+1

但是本题n的范围是10000，极端情况要计算1666 1667 0000次，评测系统一秒内只能计算1 0000 0000次，所以会超时。

正确思路✔

可以定义一个bool数组，来存前面出现过某两个数的和。

const int N2 = 1000010;

bool sum[N2];

然后遍历数组，在循环中，把a[i]和0到i - 1的数分别计算加和，把sum[a[i] + a[j]]标记为true。

再判断sum[a[i]]是否为true即可.

注意：判断应在第二重循环前，因为是在a[i]之前找数。

long long res = 0;
for (int i = 1; i < n; i ++ )
{
    if (sum[a[i]])
        res ++ ;
    for (int j = 0; j < i; j ++ )
        sum[a[i] + a[j]] = true;
}

正确代码最多计算49995000次，评测系统一秒内能计算1 0000 0000次，所以不会超时。

解题反思

做题时，使用for循环，要考虑时间复杂度

参考代码

错误思路❌ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int a[N]; // 定义数组

int main()
{
    int n;
    cin >> n; // 输入n

    for (int i = 0; i < n; i ++ ) cin >> a[i]; // 输入数组

    long long res = 0;
    for (int i = 0; i < n; i ++ ) // 最外层循环，遍历整个数组
    {
        bool ff = true; // 如果判断过这个数，就退出第二层循环
        for (int j = 0; j < i; j ++ )
        {
            if (!ff) break; // 如果找到了答案，就退出循环
            for (int k = j + 1; k < i; k ++ )
                if (a[j] + a[k] == a[i])
                {
                    ff = false;
                    res ++ ;
                    break;
                }
        }   
    }

    cout << res << endl; // 输出答案

    return 0;
}

正确思路✔ 代码

#include <bits/stdc++.h>

using namespace std;

const int N1 = 10010;

int a[N1]; // 定义输入的数组

const int N2 = 1000010;

bool sum[N2]; // 定义存和的数组

int main()
{
    int n; 
    cin >> n; // 输入n

    for (int i = 0; i < n; i ++ ) cin >> a[i]; // 输入数组

    long long res = 0; // 定义答案变量
    for (int i = 1; i < n; i ++ )
    {
        if (sum[a[i]]) // 判断如果前面两个数的和是a[i]
            res ++ ; // 答案加1
        for (int j = 0; j < i; j ++ )
            sum[a[i] + a[j]] = true; // 计算a[i] + a[j]的和
    }

    cout << res << endl; // 输出答案

    return 0;
}

笔记