C++实现黄金分割点查找算法及前缀和优化技巧

根据题目描述，我们需要找到一个下标 `i`（1 ≤ i ≤ n），使得 `a[1] + a[2] + ... + a[i]`（左侧和）等于 `a[i+1] + ... + a[n]`（右侧和）的两倍。注意分隔点可以是数组末尾（即 i = n，右侧为空，和为 0），此时条件为左侧和等于 0。同样，分隔点不能是 0（即左侧为空），因为题目要求左侧至少有元素。 直接暴力计算每个 i 的左侧和和右侧和，时间复杂度 O(n²)，对于大数据会超时。利用前缀和可以优化到 O(n)。以下是 C++ 实现： ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<long long> a(n + 1); vector<long long> prefix(n + 1, 0); for (int i = 1; i <= n; ++i) { cin >> a[i]; prefix[i] = prefix[i - 1] + a[i]; } long long total = prefix[n]; for (int i = 1; i <= n; ++i) { long long leftSum = prefix[i]; long long rightSum = total - leftSum; if (leftSum == 2 * rightSum) { cout << i << endl; return 0; } } cout << -1 << endl; return 0; } ``` **代码说明**： - 使用 `prefix` 数组存储前缀和，`prefix[i]` 表示前 i 个元素之和。 - 总和不使用单独变量，直接用 `prefix[n]`。 - 遍历 i 从 1 到 n，计算左侧和 `leftSum = prefix[i]`，右侧和 `rightSum = total - leftSum`，检查条件。 - 注意使用 `long long` 防止整数溢出。 **复杂度分析**：时间复杂度 O(n)，空间复杂度 O(n)。 ######[AI问答 | 465点数解答 | 2026-08-29 22:11:03]