题解 | #获得最多的奖金# 双指针

使用双指针从两端遍历数组，根据遍历的情况决定往左边加数还是往右边加数，

遍历完的条件是两个指针相遇，至于中间分一组这个要求，可以直接不做处理

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> d;
        long long money;
        for (int i = 0; i < n; i++) {
            cin >> money;
            d.push_back(money);
        }
        long long leftSum = d[0], rightSum = d[n - 1];
        long long ans = 0;
        long long left = 0, right = n - 1;
        while (left < right) {
            if (leftSum > rightSum) { // 左边的和大于右边的，需要往右边加一个数
                right--;
                rightSum += d[right];
            } else if (leftSum < rightSum) { // 右边的和大于左边的，需要往左边加一个数
                left++;
                leftSum += d[left];
            } else { // 两边之和相等，记录下最大和；同时往左边加一个数，推进循环
                ans = leftSum;
                left++;
                leftSum += d[left];
            }
        }
        cout << ans << endl;
    }
    return 0;
}

时间复杂度：O(n)，遍历数组

空间复杂度：O(n)，存储数组