C++数组平衡点查找算法详解与实现

我来帮你解决这个问题。这是一个经典的**数组平衡点**问题，我提供多种C++解法。 ## 🎯 问题分析 - **输入**：n个整数，范围[1, 1000] - **要求**：找到一个下标i，使得 `a[1]+...+a[i-1] == a[i+1]+...+a[n]` - **约束**：n最大100000，O(n)是必须的 ## 💡 解法一：前缀和（推荐） **核心思想**：先计算总和，再遍历，用前缀和维护左侧和。 ```cpp #include <iostream> #include <vector> using namespace std; int findBalancePoint(const vector<int>& a, int n) { long long total = 0; for (int i = 0; i < n; i++) total += a[i]; long long leftSum = 0; // 注意：边界条件（i=0或i=n-1）时左右和可为0 for (int i = 0; i < n; i++) { long long rightSum = total - leftSum - a[i]; if (leftSum == rightSum) return i + 1; // 返回1-based下标 leftSum += a[i]; } return -1; // 未找到 } int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; int result = findBalancePoint(a, n); if (result != -1) cout << "平衡点下标（1-based）: " << result << endl; else cout << "不存在平衡点" << endl; return 0; } ``` ## 📊 解法二：双指针（空间优化版） **优点**：只需一次遍历，但需要额外判断。 ```cpp #include <iostream> using namespace std; int findBalancePointEfficient(int a[], int n) { long long rightSum = 0, leftSum = 0; // 先计算总和 for (int i = 0; i < n; i++) rightSum += a[i]; for (int i = 0; i < n; i++) { rightSum -= a[i]; // 当前元素从右侧移除 if (leftSum == rightSum) return i + 1; leftSum += a[i]; // 当前元素加入左侧 } return -1; } ``` ## ⚠️ 关键注意事项 1. **整数溢出**：n最大100000，a[i]最大1000，总和最大为 100000×1000 = **10^8**，超过int范围，必须用`long long`。 2. **边界情况**： - 当 `i=0` 时，左侧和=0，要判断 total - a[0] 是否等于0 - 当 `i=n-1` 时，右侧和=0 3. **多平衡点**：题目只要求找到一个，代码返回第一个即可。 ## 🚀 测试示例 ``` 输入： 5 1 2 3 4 6 输出： 平衡点下标（1-based）: 4 （因为1+2+3=6，右侧=6） ``` ## 📚 进阶优化建议 - **若存在多个平衡点**：可以用vector存储所有结果 - **若数据量大**：考虑使用`std::ios::sync_with_stdio(false)`加速输入输出 - **通用性**：可以将`int`改为模板类型支持浮点数 ## ✅ 复杂度分析 - **时间复杂度**：O(n)，一次遍历 - **空间复杂度**：O(1)，只使用常数空间（假设原数组已存储） ######[AI写代码神器 | 850点数解答 | 2026-07-31 20:20:39]