解题思路

算式是：1 + (1+2) + (1+2+3) + …… + (1+2+…+n)。第 i 个括号里是从 1 加到 i 的和。

最笨的方法是每个括号都重新算一遍，但那样很慢，也不"巧妙"。更聪明的做法是：用一个变量 s 表示"当前这个括号的和"。相邻两个括号有个规律：

第 i 个括号是 1+2+…+i； 第 i+1 个括号是 1+2+…+i+(i+1)。

也就是说，新的括号只是在旧的括号基础上多加了 (i+1) 而已！所以我们每次让 s=s+i（在旧括号和上加 i），就能得到新括号的和，不用重算。

再用一个变量 sum 把所有括号的和累加起来：sum=sum+s。循环完就得到答案。

验证样例：n=6 时，各个括号分别是 1、3、6、10、15、21，加起来 1+3+6+10+15+21=56，和样例一致。

参考代码

#include <iostream>
using namespace std;

int main() {
    int n;              // n：算式中最大的数
    cin >> n;           // 读入 n
    int s = 0;          // s：当前这个括号 1+2+...+i 的和
    int sum = 0;        // sum：所有括号加起来的总和（答案）
    for (int i = 1; i <= n; i++) {
        s = s + i;      // 新括号比旧括号多加了 i
        sum = sum + s;  // 把当前括号的和累加到答案上
    }
    cout << sum << endl; // 输出结果
    return 0;
}

复杂度分析

只循环 n 次，每次做两次加法，时间复杂度是 O(n)，其中 n 是算式中最大的数。n≤100，循环 100 次就能得到答案，非常快。空间上只用 n、s、sum、i 四个变量，空间复杂度 O(1)。