C++中sumUpToNumber函数及调用代码的性能优化求助

原代码耗时久的核心原因是线性遍历次数过多（需迭代约65536次才能找到结果），且存在类型截断导致的判断逻辑隐患。以下是几种可行的优化方案：

1. 数学公式直接计算（最优解） #

利用累加和公式推导直接求解最大N，无需循环，时间复杂度O(1)。

累加和公式为 ( S = \frac{n(n+1)}{2} )，要求 ( S \leq INT_MAX )，变形为二次不等式：
[ n^2 + n - 2 \times INT_MAX \leq 0 ]
求解正根得到：
[ n = \frac{-1 + \sqrt{1 + 8 \times INT_MAX}}{2} ]
取该值的整数部分即为目标N。

代码实现：

#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

int main() {
    // 用long long避免计算判别式时溢出
    long long discriminant = 1LL + 8LL * INT_MAX;
    int max_n = static_cast<int>((sqrt(discriminant) - 1) / 2);
    cout << "Maximum number N before overflow is: " << max_n << endl;
    return 0;
}

2. 修复类型问题并终止循环 #

原代码中sum为int类型，接收long类型的返回值会发生截断，导致判断条件失真；同时找到结果后未终止循环，做了大量无用迭代。

优化后的线性遍历代码：

#include <iostream>
#include <climits>

using namespace std;

long sumUpToNumber(int n) {
    // 先将n转为long，避免n*(n+1)时int溢出
    return static_cast<long>(n) * (n + 1) / 2;
}

int main() {
    for (int i = 1; ; i++) {
        long sum = sumUpToNumber(i);
        if (sum >= INT_MAX) {
            cout << "Maximum number N before overflow is: " << i - 1 << endl;
            break; // 找到结果立即终止循环
        }
    }
    return 0;
}

3. 二分查找优化遍历效率 #

若需保留循环逻辑，用二分查找替代线性遍历，将时间复杂度从O(n)降至O(logn)，仅需约17次迭代即可找到结果。

代码实现：

#include <iostream>
#include <climits>

using namespace std;

long sumUpToNumber(int n) {
    return static_cast<long>(n) * (n + 1) / 2;
}

int main() {
    int left = 1, right = 200000; // 初始范围设为足够覆盖目标值
    int max_n = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 避免mid计算时溢出
        long sum = sumUpToNumber(mid);
        if (sum <= INT_MAX) {
            max_n = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << "Maximum number N before overflow is: " << max_n << endl;
    return 0;
}

内容的提问来源于stack exchange，提问作者DannyBoy