大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
51goc 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;
}
笔记
| 复杂度 | 数量级 | 最大规模 |
|---|---|---|
| O(logN) | >> 10 ^ 20 | 很大 |
| O(N^1 / 2) | 10 ^ 12 | 10 ^ 14 |
| O(N) | 10 ^ 6 | 10 ^ 7 |
| O(NlogN) | 10 ^ 5 | 10 ^ 6 |
| O(N ^ 2) | 1000 | 2500 |
| O(N ^ 3) | 100 | 500 |
| O(N ^ 4) | 50 | 50 |
| O(2 ^ N) | 20 | 20 |
| O(3 ^ N) | 14 | 15 |
| O(N!) | 9 | 10 |
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/167888.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
