题意

求等差数列:2,5,8... 前n项的和

限制: n 不大于1000

方法

循环遍历

我们循环n次

每次计算当前位置的值,并将它放入总和里

最后输出总和即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        int ans = 0;
        int v = 2;
        for(int i = 0;i<n;i++){// 遍历 n 次
            ans += v; // 加到总和里
            v+=3; // 下一个位置的值
        }
        printf("%d\n",ans);
    }
    return 0;
}

复杂度分析

时间复杂度: 遍历了n次,每次操作常数代价,所以总时间复杂度为$O(n)O(n)$

空间复杂度: 我们用了常数个额外变量,所以空间复杂度为$O(1)O(1)$

数学

我们把求和数列与其逆序相加

所以 两倍和 = $n(1+3n)n(1+3n)$

所以 和 = $\frac{n(1+3n)}{2}\backslash frac\{n(1+3n)\}2$

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        printf("%d\n",(1+3*n)*n/2);
    }
    return 0;
}

复杂度分析

时间复杂度: 我们每次通过数学公式计算,直接计算出答案,所以时间复杂度为$O(1)O(1)$

空间复杂度: 我们用了常数个额外变量,所以空间复杂度为$O(1)O(1)$