C#计算数组嵌套前缀和总和的实现问题求解

需求说明 #

需要计算数组的嵌套求和，即所有从首元素开始的前缀和的累加总值。以测试数组[1,2,2,3,6]为例，计算规则：
依次计算各长度前缀的和：

• 长度1前缀：0 + 1 = 1
• 长度2前缀：1 + 2 = 3
• 长度3前缀：1 + 2 + 2 = 5
• 长度4前缀：1 + 2 + 2 + 3 = 8
• 长度5前缀：1 + 2 + 2 + 3 + 6 = 14
  最终求和结果为1 + 3 + 5 + 8 + 14 = 31。

原有代码的问题 #

你提供的栈实现存在两个核心逻辑错误：

1. 压栈阶段仅存入了原始数组元素，没有记录每一步的前缀累加值，完全缺失前缀和计算逻辑
2. 栈是后进先出结构，按原数组顺序压入后弹出的是数组逆序元素，且代码跳过了第一次弹出的元素，最终计算结果仅为数组从第二个元素开始的总和，和需求完全不匹配。

正确实现 #

方案1：最优一次遍历实现（推荐） #

时间复杂度O(n)，空间复杂度O(1)，不需要额外栈结构，遍历过程中维护当前前缀和，同步累加到最终结果即可：

int CalTotalPrefixSum(int[] queries)
{
    int totalSum = 0;
    int currentPrefix = 0;
    foreach (int num in queries)
    {
        currentPrefix += num;
        totalSum += currentPrefix;
    }
    return totalSum;
}

传入测试数组[1,2,2,3,6]时，执行流程：

• 遍历元素1：当前前缀和为1，总累加值为1
• 遍历元素2：当前前缀和为3，总累加值为1+3=4
• 遍历元素2：当前前缀和为5，总累加值为4+5=9
• 遍历元素3：当前前缀和为8，总累加值为9+8=17
• 遍历元素6：当前前缀和为14，总累加值为17+14=31
  返回结果完全符合预期。

方案2：基于Stack的实现 #

如果需要沿用栈的实现思路，要在压栈阶段就计算并存储每一步的前缀和，而不是只存原始元素：

int CalTotalPrefixSumWithStack(int[] queries)
{
    int totalSum = 0;
    Stack<int> prefixStack = new Stack<int>();
    int currentPrefix = 0;
    // 遍历计算所有前缀和压入栈
    for (int i = 0; i < queries.Length; i++)
    {
        currentPrefix += queries[i];
        prefixStack.Push(currentPrefix);
    }
    // 弹出栈内所有前缀和累加
    while (prefixStack.Count > 0)
    {
        totalSum += prefixStack.Pop();
    }
    return totalSum;
}

该实现同样可以得到正确结果31，但会额外占用O(n)的栈空间，无特殊要求时优先选择方案1。

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