【优选算法篇】解密前缀和：让数组求和变得如此高效（上篇）

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

1. C++ 前缀和算法 详解

1.1 前缀和算法的重要性

前缀和算法是解决一类常见数组问题的高效方法。它的核心价值在于将多次重复计算的部分进行优化，使得对数组的多次区间求和操作能在常数时间内完成。它不仅可以大幅减少时间复杂度，还能够应用于各种问题，如数组求和、子数组的最大/最小和等。

前缀和算法常被用在求区间和、数据查询、动态规划等场景，是程序员处理大规模数据时的必备工具。

1.2 什么是前缀和？

前缀和（Prefix Sum）是一个数组的派生数组，其中每个元素表示原数组中从第一个元素到该位置元素的累积和。

给定一个数组 A = [a1, a2, a3, ..., an]，前缀和数组 S 由下列公式构成： S[i]=A[1]+A[2]+...+A[i] 其中 S[0]=0 以方便进行区间和的计算。

例子：

对于数组 A = [1, 2, 3, 4, 5]，前缀和数组 S 为：

• S[0] = 0
• S[1] = 1 (即 A[1])
• S[2] = 1 + 2 = 3
• S[3] = 1 + 2 + 3 = 6
• S[4] = 1 + 2 + 3 + 4 = 10
• S[5] = 1 + 2 + 3 + 4 + 5 = 15

因此，前缀和数组 S = [0, 1, 3, 6, 10, 15]。

1.3 前缀和的核心思想

前缀和的核心思想是通过预处理累加和，使得可以快速计算任意区间的和。通过这个方法，我们避免了每次都重复计算区间和的冗余操作，将时间复杂度从 O(n) 降到 O(1)。

具体来说：

1. 预处理阶段：首先，构造前缀和数组，这一步的时间复杂度是 O(n)。
2. 查询阶段：利用前缀和数组，计算任意区间 [i, j] 的和，只需要 O(1) 的时间。区间和可以通过以下公式得到： 区间和=S[j]−S[i−1]
3. 这样，求区间和的操作不再是 O(n)，而是 O(1)，大大提高了效率。

1.4 前缀和的经典应用

1. 区间求和问题 前缀和最直接的应用就是快速求解区间和。对于给定的数组 A，如果需要计算区间 [i, j] 的和，传统方法需要遍历该区间，而使用前缀和可以通过一次减法操作直接得到答案。 问题描述：给定一个数组，求数组中从第 i 个元素到第 j 个元素的和。 解决方法：通过前缀和数组，区间和为： sum[i,j] = S[j] − S[i−1]
2. 子数组和的最大值/最小值 给定一个数组，求其所有子数组的和的最大值或最小值。通过前缀和数组，可以在 O(n) 的时间内计算所有子数组的和，进而找到最大值或最小值。
3. 动态规划 前缀和算法常用于动态规划问题，尤其是在涉及到累积和的题目中。例如，在处理有序数组和区间查询问题时，前缀和数组能够有效地减少复杂度。
4. 大数据问题 在处理大规模数据集时，前缀和的效率尤为重要。例如，在时间序列分析中，要求快速求解特定时间段的总和时，前缀和可以显著加速查询过程。
5. 数列统计问题 例如，在“动态区间求和”和“区间更新问题”中，前缀和可以帮助我们快速统计数组的特定部分，减少了重复计算的开销。

2. 题目1：DP34 【模板】前缀和

2.1 题目链接：【模板】前缀和_牛客题霸_牛客网

题目描述：

本题较简单

2.1 算法思路：

这个程序的核心思想是利用 前缀和 来解决 区间求和 问题，使得每次查询的时间复杂度从 O(n) 降低到 O(1)。

2.2 示例代码：

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

int main() 
{
    // 读入n和q，n是数组的大小，q是查询的次数
    int n, q;
    cin >> n >> q;

    // 创建一个大小为n+1的数组a，用来存储输入的元素，a[0]不使用
    vector<int> a(n + 1);

    // 读入数组a的元素，注意a的下标从1开始
    for(int i = 1; i <= n; i++) 
        cin >> a[i];

    // 创建一个大小为n+1的前缀和数组dp
    vector<long long> dp(n + 1);

    // 预处理前缀和数组dp，其中dp[i]表示从a[1]到a[i]的元素和
    for(int i = 1; i <= n; i++) 
    {
        dp[i] = dp[i - 1] + a[i]; // dp[i] = dp[i-1] + a[i]，即dp[i]存储前i项的累积和
    }

    // 处理q个查询
    while(q--) 
    {
        // 读取查询的区间[l, r]
        int l, r;
        cin >> l >> r;

        // 计算区间[l, r]的和，利用前缀和公式：sum[l, r] = dp[r] - dp[l-1]
        long long ret = dp[r] - dp[l - 1];

        // 输出查询结果
        cout << ret << endl;
    }

    return 0;
}

2.3.1 代码的详细解析：

2.3.1.1 输入数据

int n, q; cin >> n >> q; vector<int> a(n + 1);

• n：数组 a 的大小，即数组的元素个数。
• q：查询的次数，即我们需要进行 q 次区间求和查询。
• vector<int> a(n + 1)：这是一个大小为 n + 1 的数组，用来存储输入的数组元素。多加一个元素的空间是为了方便下标从 1 开始，避免数组下标越界。

2.3.1.2 输入数组元素

for (int i = 1; i <= n; i++) cin >> a[i];

• 通过循环将数组 a 的元素从输入中读取。注意，数组的下标从 1 开始，所以 a[0] 并不使用。

2.3.1.3 计算前缀和

vector<long long> dp(n + 1); // 预处理前缀和 dp 数组 for (int i = 1; i <= n; i++) { dp[i] = dp[i - 1] + a[i]; }

• vector<long long> dp(n + 1)：定义一个大小为 n + 1 的 dp 数组来存储前缀和，使用 long long 类型以防止溢出。
• dp[i] = dp[i - 1] + a[i]：这是前缀和的计算方式。dp[i] 表示数组 a 中从 a[1] 到 a[i] 的和。通过累加得到前缀和数组。这样，dp[i] 就是数组 a 的前 i 项的累积和。
  • 比如，假设 a = [1, 2, 3, 4, 5]，那么：
    • dp[1] = a[1]
    • dp[2] = a[1] + a[2]
    • dp[3] = a[1] + a[2] + a[3]
    • 依此类推，dp[i] = a[1] + a[2] + ... + a[i]

2.3.1.4 处理查询

while (q--) { int l, r; cin >> l >> r; long long ret = dp[r] - dp[l - 1]; cout << ret << endl; }

• while (q--)：循环执行 q 次查询。
• cin >> l >> r：每次查询给定一个区间 [l, r]，即需要计算数组 a 中从下标 l 到下标 r 的元素和。
• long long ret = dp[r] - dp[l - 1]：
  • 由于 dp 数组保存的是前缀和，区间 [l, r] 的和可以通过 dp[r] - dp[l-1] 直接计算。
  • 这里的 dp[r] 是从 a[1] 到 a[r] 的和，dp[l-1] 是从 a[1] 到 a[l-1] 的和。两者相减即得到区间 [l, r] 的和。
• cout << ret << endl;：输出结果。

2.3 时间与空间复杂度

• 时间复杂度：
  • 前缀和计算：计算前缀和的时间复杂度是 O(n)，因为每个元素只需要访问一次。
  • 每个查询：对于每个查询，计算区间和的时间复杂度是 O(1)，因为查询是通过前缀和数组直接减法得到结果。
  • 总的时间复杂度是 O(n + q)，其中 n 是数组的大小，q 是查询次数。
• 空间复杂度：空间复杂度是 O(n)，因为使用了一个额外的数组 dp 来存储前缀和。

2.4 补充（可看可不看）

2.4.1 暴力解法

暴力解法就是直接根据查询的区间去计算该区间的和，即对于每一个查询，遍历数组从 a[l] 到 a[r]，直接求和。每次查询的时间复杂度是 O(r - l + 1)，也就是每次查询都遍历一次区间。

具体步骤：

1. 输入数组的长度 n 和查询的次数 q。
2. 输入数组 a 的元素。
3. 对于每次查询，给定 l 和 r，计算数组 a 从 l 到 r 的和。
4. 输出每次查询的结果。

2.4.2 示例代码：

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

int main() 
{
    // 输入n和q，n是数组大小，q是查询次数
    int n, q;
    cin >> n >> q;

    // 输入数组a，大小为n
    vector<int> a(n + 1);  // 多加一个元素来让下标从1开始
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 处理q次查询
    while (q--) {
        int l, r;
        cin >> l >> r;

        // 计算区间[l, r]的和（暴力解法：遍历区间内的元素）
        long long sum = 0;
        for (int i = l; i <= r; i++) {
            sum += a[i];  // 累加区间内的元素
        }

        // 输出结果
        cout << sum << endl;
    }

    return 0;
}

2.4.2.1 解析

• 输入部分：
  • cin >> n >> q; 读取数组长度 n 和查询次数 q。
  • 使用 vector<int> a(n + 1) 来存储数组 a，并且通过循环输入数组元素，数组的下标从 1 开始。
• 查询部分：
  • 对于每个查询，输入 l 和 r，表示需要求 a[l] 到 a[r] 的元素和。
  • 使用一个 for 循环来遍历数组的区间 [l, r]，然后累加区间内的所有元素。
  • 最后输出该区间的和。
• 暴力解法：
  • 每次查询时直接遍历区间 [l, r]，时间复杂度为 O(r - l + 1)，即遍历该区间的所有元素。

2.4.2.2 时间复杂度分析

• 对于每个查询，时间复杂度是 O(r - l + 1)，即查询区间的大小。
• 如果所有查询的总区间长度大致为 O(n)，则最坏情况下的总时间复杂度为 O(q * n)，其中 q 是查询次数，n 是数组的大小。
  • 例如，如果每次查询的区间几乎包含整个数组，那么总的时间复杂度会达到 O(q * n)，这在查询次数较多时会导致程序运行缓慢。

2.4.3 优化方向

虽然暴力解法直观且简单，但它的效率较低，尤其是当 q 较大时，会导致 O(q * n) 的时间复杂度。为了优化该算法，可以使用 前缀和 技术。通过预先计算出前缀和数组，可以在 O(1) 时间内处理每次查询，将总时间复杂度降低为 O(n + q)，从而大大提高效率。

2.5 总结：

这个程序的核心思想是通过前缀和来优化区间求和问题，预处理一步后，每次查询可以在常数时间内得到结果。对于多个查询的场景，前缀和算法能显著减少查询的时间复杂度，是处理大规模数据时非常有效的技术。

3. 题目2：模板】二维前缀和

题目链接：【模板】二维前缀和_牛客题霸_牛客网

题目描述：

3.1 算法思路：

1. 二维前缀和的定义：
   • 前缀和数组 dp[i][j] 表示矩阵中从 (1, 1) 到 (i, j) 的矩形区域的元素和。
   • 计算方法： dp[i][j] = a[i][j] + dp[i−1][j] + dp[i][j−1] − dp[i−1][j−1] 这个公式通过前面已经计算过的区域合并当前元素 a[i][j]，并减去重复计算的部分 dp[i-1][j-1]。
2. 查询区域和：
   • 给定查询区域的左上角 (x1, y1) 和右下角 (x2, y2)，子矩阵的和可以通过二维前缀和数组 dp 直接计算： sum(x1,y1,x2,y2) = dp[x2][y2] − dp[x1−1][y2] − dp[x2][y1−1] + dp[x1−1][y1−1] 这个公式通过包含与排除法得到目标区域的和。

步骤解析

1. 输入数据：
   • 输入矩阵的大小 n 和 m，以及查询的次数 q。
   • 然后读取矩阵元素，并存储到二维数组 a 中。
2. 前缀和矩阵计算：
   • 初始化一个二维数组 dp，其中 dp[i][j] 存储从 (1, 1) 到 (i, j) 的矩阵和。
   • 使用嵌套循环遍历矩阵并计算 dp[i][j]。
3. 处理查询：
   • 对于每次查询，利用前缀和矩阵 dp 计算出所需区域的和并输出。

3.2 示例代码：

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

int main() 
{
    // 1. 读入数据
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> a(n + 1, vector<int>(m + 1));
    
    // 输入矩阵a，注意从下标1开始
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    // 2. 预处理前缀和矩阵dp
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    
    // 计算二维前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + a[i][j] - dp[i - 1][j - 1];
        }
    }

    // 3. 处理查询
    int x1, y1, x2, y2;
    while (q--) {
        cin >> x1 >> y1 >> x2 >> y2;
        
        // 计算并输出查询的区域和
        long long result = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
        cout << result << endl;
    }

    return 0;
}

3.2.1 详细解释

1. 二维前缀和矩阵 dp 的计算：
   • dp[i][j] 表示矩阵从 (1, 1) 到 (i, j) 的元素和。通过以下公式计算： dp[i][j] = a[i][j] + dp[i−1][j] + dp[i][j−1] − dp[i−1][j−1] 这一步是在 O(n * m) 时间复杂度内完成的。
2. 查询处理：
   • 每个查询给定一个子矩阵的左上角 (x1, y1) 和右下角 (x2, y2)，要计算这个子矩阵的和。
   • 利用前缀和数组 dp，可以在 O(1) 的时间内得到子矩阵的和： sum(x1,y1,x2,y2) = dp[x2][y2] − dp[x1−1][y2] − dp[x2][y1−1] + dp[x1−1][y1−1] 这个计算是通过包含与排除法得出的，即通过加上 (x2, y2) 范围的和，减去不需要的区域，然后加上被减去两次的交集部分。

3.3 时间复杂度分析

• 前缀和计算：
  • 构造前缀和矩阵 dp 需要遍历整个矩阵，因此时间复杂度为 O(n * m)。
• 每个查询：
  • 每次查询都能在常数时间内 O(1) 得到结果，因为通过前缀和数组可以快速计算任意子矩阵的和。
• 总体时间复杂度：
  • 预处理时间为 O(n * m)。
  • 查询处理时间为 O(q)，每个查询的处理时间是 O(1)。
  • 因此，总体时间复杂度为 O(n * m + q)，其中 n 和 m 是矩阵的维度，q 是查询的次数。

空间复杂度

• a 和 dp 数组的大小均为 O(n * m)，因此空间复杂度为 O(n * m)。

3.4 补充（可看可不看）

3.4.1 暴力解法

步骤：

1. 输入数据：首先，读入矩阵的尺寸 n x m 和查询次数 q。
2. 矩阵输入：接着读入矩阵的元素。
3. 处理查询：对于每次查询，使用嵌套循环遍历矩阵中的区间 [x1, y1] 到 [x2, y2]，然后求出该区间的和。
4. 输出结果：每次查询的结果直接输出。

3.4.2 示例代码：

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

int main() 
{
    // 1. 输入矩阵的行数、列数和查询次数
    int n, m, q;
    cin >> n >> m >> q;

    // 2. 输入矩阵元素
    vector<vector<int>> a(n + 1, vector<int>(m + 1));  // 使用 n+1, m+1 以便从1开始
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    // 3. 处理查询
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        long long sum = 0; // 存储当前查询区域的和
        // 暴力计算子矩阵的和
        for (int i = x1; i <= x2; i++) {
            for (int j = y1; j <= y2; j++) {
                sum += a[i][j];
            }
        }

        // 输出当前查询的结果
        cout << sum << endl;
    }

    return 0;
}

3.4.2.1 代码解释

1. 输入部分：
   • cin >> n >> m >> q;：读入矩阵的行数 n、列数 m 和查询次数 q。
   • 使用 vector<vector<int>> a(n + 1, vector<int>(m + 1)); 来存储矩阵 a。+1 是为了方便将矩阵的下标从 1 开始。这样，a[1][1] 就是矩阵的第一个元素。
2. 矩阵元素输入：
   • 使用嵌套的 for 循环输入矩阵的每一行每一列元素。
3. 查询处理：
   • 对于每个查询，输入 x1, y1, x2, y2，表示查询的矩形区域的左上角 (x1, y1) 和右下角 (x2, y2)。
   • 使用两层循环，遍历从 (x1, y1) 到 (x2, y2) 的所有元素，累加它们的和。
4. 输出：
   • 输出每次查询的结果，即计算得到的子矩阵的和。

3.4.2.2 时间复杂度分析

对于每次查询，我们需要遍历一个矩形区域，该区域的大小为 (x2 - x1 + 1) * (y2 - y1 + 1)。因此，最坏情况下，如果查询的区域几乎是整个矩阵，则每个查询需要 O(n * m) 的时间复杂度。

• 时间复杂度：
  • 每次查询的时间复杂度是 O((x2 - x1 + 1) * (y2 - y1 + 1))，在最坏情况下是 O(n * m)。
  • 对于 q 次查询，总的时间复杂度是 O(q * n * m)。
• 空间复杂度：
  • 存储矩阵的空间复杂度是 O(n * m)。

3.4.3 优化方向

暴力解法虽然简单直观，但它在处理大规模矩阵或大量查询时效率较低。为了优化，可以使用 前缀和 技术，在预处理阶段构造一个前缀和矩阵，使得每次查询的时间复杂度从 O(n * m) 降到 O(1)。

3.5 总结：

通过使用二维前缀和技术，我们能够在 O(1) 时间内处理每个查询，这大大提高了查询效率。虽然前期需要花费 O(n * m) 的时间来构建前缀和矩阵，但这在处理大量查询时能够显著减少整体时间复杂度。

4. 题目3：寻找数组的中心下标

题目链接：724. 寻找数组的中心下标 - 力扣（LeetCode）

题目描述：

4.1 算法思路：

主要思路

该算法通过计算数组的 前缀和 和 后缀和 来解题。具体思路如下：

1. 前缀和 (dp1)：dp1[i] 代表从数组开始到索引 i-1 的所有元素之和。
   • 例如，dp1[3] 就是数组中 nums[0] + nums[1] + nums[2]。
2. 后缀和 (dp2)：dp2[i] 代表从索引 i+1 到数组末尾的所有元素之和。
   • 例如，dp2[3] 就是数组中 nums[4] + nums[5]（假设数组长度为6）。

通过这两个数组，dp1 存储了每个位置左边的和，dp2 存储了每个位置右边的和。我们可以通过比较这两个数组在同一位置的值来找出符合条件的 pivot index。

算法步骤

1. 计算前缀和 (dp1)：
   • 对于每个位置 i，dp1[i] 存储从数组 nums[0] 到 nums[i-1] 的元素和。
2. 计算后缀和 (dp2)：
   • 对于每个位置 i，dp2[i] 存储从数组 nums[i+1] 到数组 nums[n-1] 的元素和。
3. 判断是否为 pivot index：
   • 对于每个索引 i，如果 dp1[i] 等于 dp2[i]，则返回该索引 i。
4. 返回结果：
   • 如果没有找到符合条件的索引，返回 -1。

4.2 示例代码：

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        
        // 创建前缀和数组 dp1 和后缀和数组 dp2
        vector<int> dp1(n, 0); // 前缀和
        vector<int> dp2(n, 0); // 后缀和

        // 计算前缀和 dp1
        for (int i = 1; i < n; i++) {
            dp1[i] = dp1[i - 1] + nums[i - 1];
        }

        // 计算后缀和 dp2
        for (int i = n - 2; i >= 0; i--) {
            dp2[i] = nums[i + 1] + dp2[i + 1];
        }

        // 遍历数组，检查是否满足 pivot index 条件
        for (int i = 0; i < n; i++) {
            if (dp1[i] == dp2[i]) {
                return i;  // 返回找到的 pivot index
            }
        }

        return -1;  // 如果没有找到，返回 -1
    }
};

4.2.1 代码步骤详细解析

1. 初始化 dp1 和 dp2：
   • dp1[i] 表示索引 i 左边的和，初始化时所有元素设为 0。
   • dp2[i] 表示索引 i 右边的和，初始化时所有元素设为 0。
2. 计算 dp1：
   • dp1[i] 通过逐步累加数组元素实现，从 i=1 开始，每次将前一个元素的和加上当前的 nums[i-1]。
3. 计算 dp2：
   • dp2[i] 通过从后向前遍历数组计算，对于每个位置 i，dp2[i] 为 nums[i+1] + dp2[i+1]。
4. 查找 pivot index：
   • 最后遍历整个数组，比较每个位置的 dp1[i] 和 dp2[i]，如果相等，说明找到了 pivot index。
5. 返回结果：
   • 如果找到了满足条件的索引 i，直接返回该索引。如果遍历结束后没有找到符合条件的索引，则返回 -1。

4.2.2 优化建议

尽管该方法时间复杂度为 O(n)，但是它使用了额外的 O(n) 空间来存储前缀和和后缀和。实际上，我们可以在不使用额外空间的情况下优化该算法，直接使用一个变量来保存前缀和，并计算右边的和。这样可以将空间复杂度降到 O(1)。

改进版：空间优化（不使用额外的 dp1 和 dp2 数组）

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int total_sum = 0;
        int left_sum = 0;
        
        // 计算总和
        for (int num : nums) {
            total_sum += num;
        }

        // 遍历数组，计算每个位置的左右和
        for (int i = 0; i < nums.size(); i++) {
            // 右和 = 总和 - 左和 - 当前元素
            if (left_sum == total_sum - left_sum - nums[i]) {
                return i;
            }
            left_sum += nums[i];  // 更新左和
        }

        return -1;  // 如果没有找到，返回 -1
    }
};

4.2.2.1 优化后的时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是数组的长度，因为我们遍历了数组两次：一次计算总和，一次查找 pivot index。
• 空间复杂度：O(1)，我们只用了常数空间。

4.2.3 总结

• 暴力解法：使用前缀和和后缀和的方式可以在 O(n) 时间内求解，但需要额外的 O(n) 空间。
• 优化解法：通过维护一个左边的和 left_sum 和计算右边的和 total_sum - left_sum - nums[i]，我们能够将空间复杂度降低到 O(1)，并且保持时间复杂度为 O(n)。

4.3 复杂度分析

时间复杂度

• 构造 dp1 和 dp2：
  • dp1 和 dp2 数组的计算需要遍历数组一次，每次遍历的时间复杂度是 O(n)。
• 遍历数组查找 pivot index：
  • 需要遍历一遍数组来比较 dp1[i] 和 dp2[i]，也是 O(n)。

因此，整体时间复杂度为 O(n)，其中 n 是数组的长度。

空间复杂度

• 额外使用了两个数组 dp1 和 dp2，每个数组的大小都是 n，因此空间复杂度为 O(n)。

4.4 补充（可看可不看）

4.4.1 暴力解法

暴力解法的思路非常简单：对于每个元素，计算该元素左边和右边的和，判断是否相等。如果相等，就返回该索引。

解决思路

1. 遍历每个元素：我们可以遍历数组的每个索引 i，对于每个索引 i，计算其左边的和 sum_left 和右边的和 sum_right。
2. 左边和的计算：对于每个索引 i，左边的和就是 nums[0] + nums[1] + ... + nums[i-1]。
3. 右边和的计算：对于每个索引 i，右边的和就是 nums[i+1] + nums[i+2] + ... + nums[n-1]。
4. 比较左右和：如果左右和相等，则返回当前索引 i。如果遍历完所有索引没有找到符合条件的索引，则返回 -1。

4.4.2 示例代码：

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        
        // 遍历每个索引，计算左右两边的和
        for (int i = 0; i < n; i++) {
            int sum_left = 0, sum_right = 0;
            
            // 计算左边的和
            for (int j = 0; j < i; j++) {
                sum_left += nums[j];
            }
            
            // 计算右边的和
            for (int j = i + 1; j < n; j++) {
                sum_right += nums[j];
            }

            // 判断是否是 pivot index
            if (sum_left == sum_right) {
                return i; // 找到满足条件的 pivot index
            }
        }
        
        // 如果没有找到 pivot index，返回 -1
        return -1;
    }
};

4.4.2.1 代码分析

1. 外层循环：遍历数组的每个元素 i，依次尝试每个索引作为 pivot index。
2. 内层循环：分别计算该索引的左边和右边的和：
   • 左边的和是从 0 到 i-1 的所有元素之和。
   • 右边的和是从 i+1 到 n-1 的所有元素之和。
3. 比较左右和：如果左边和等于右边和，则返回当前的索引 i。
4. 返回 -1：如果遍历完所有索引仍然没有找到符合条件的 pivot index，则返回 -1。

4.4.2.2 复杂度分析

时间复杂度分析

• 外层循环：遍历数组的每个索引，总共有 n 次迭代。
• 内层循环：每次需要计算左右两边的和：
  • 计算左边和时，从 0 到 i-1 遍历元素，时间复杂度是 O(i)。
  • 计算右边和时，从 i+1 到 n-1 遍历元素，时间复杂度是 O(n-i-1)。

  因此，对于每个索引 i，内层循环的时间复杂度是 O(n)。

• 总体时间复杂度是 O(n^2)，其中 n 是数组的长度。

空间复杂度分析

• 暴力解法不需要额外的空间来存储其他数据，只有少数几个变量，因此空间复杂度是 O(1)。

4.4.3 总结

• 时间复杂度：O(n^2)，因为每次查询都需要遍历一部分数组来计算左边和和右边和。
• 空间复杂度：O(1)，因为没有使用额外的数组，仅使用了常数空间。

暴力解法虽然简单直观，但当数组的长度很大时，性能会变得非常差，因此在实际应用中，通常会尝试使用更加高效的解法（如前缀和、后缀和等）。

4.5 总结

• 暴力解法：使用前缀和和后缀和的方式可以在 O(n) 时间内求解，但需要额外的 O(n) 空间。
• 优化解法：通过维护一个左边的和 left_sum 和计算右边的和 total_sum - left_sum - nums[i]，我们能够将空间复杂度降低到 O(1)，并且保持时间复杂度为 O(n)。

5. 题目4：除自身以外数组的乘积

题目链接：238. 除自身以外数组的乘积 - 力扣（LeetCode）

题目描述：

5.1 算法思路：

具体思路如下：

1. 前缀积 (dp1)：

dp1[i] 表示数组 nums 中从索引 0 到 i-1 的所有元素的乘积（不包括 nums[i]）。我们通过一个从左到右的遍历来填充 dp1 数组。

• dp1[0] = 1，因为左边没有任何元素。
• 对于每个 i，我们有 dp1[i] = dp1[i-1] * nums[i-1]，即 dp1[i] 是 dp1[i-1] 与 nums[i-1] 的乘积。

2. 后缀积 (dp2)：

dp2[i] 表示数组 nums 中从索引 i+1 到 n-1 的所有元素的乘积（不包括 nums[i]）。我们通过一个从右到左的遍历来填充 dp2 数组。

• dp2[n-1] = 1，因为右边没有任何元素。
• 对于每个 i，我们有 dp2[i] = dp2[i+1] * nums[i+1]，即 dp2[i] 是 dp2[i+1] 与 nums[i+1] 的乘积。

3. 最终答案：

最后，数组 answer[i] 就是 dp1[i] 与 dp2[i] 的乘积。因为 dp1[i] 包含了索引 i 左边所有元素的乘积，dp2[i] 包含了索引 i 右边所有元素的乘积，因此 dp1[i] * dp2[i] 就是索引 i 左右两边所有元素的乘积。

5.2 示例代码：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        
        // 初始化前缀积和后缀积数组
        vector<int> dp1(n, 1); // dp1[i] 存储从 0 到 i-1 的乘积
        vector<int> dp2(n, 1); // dp2[i] 存储从 i+1 到 n-1 的乘积

        // 填充 dp1 数组
        for (int i = 1; i < n; i++) {
            dp1[i] = dp1[i - 1] * nums[i - 1];
        }

        // 填充 dp2 数组
        for (int i = n - 2; i >= 0; i--) {
            dp2[i] = dp2[i + 1] * nums[i + 1];
        }

        // 计算答案数组
        vector<int> answer(n);
        for (int i = 0; i < n; i++) {
            answer[i] = dp1[i] * dp2[i];
        }

        return answer;
    }
};

5.2.1 代码解析

1. 初始化：
   • dp1 和 dp2 都是大小为 n 的数组，初始值都设置为 1。这表示 dp1 和 dp2 的初始状态分别是 "空数组" 的乘积（即 1）。
2. 填充 dp1：
   • dp1[i] 存储从 0 到 i-1 索引的乘积。
   • 对于 i = 1，dp1[1] = nums[0]，对于 i = 2，dp1[2] = nums[0] * nums[1]，依此类推。
3. 填充 dp2：
   • dp2[i] 存储从 i+1 到 n-1 索引的乘积。
   • 对于 i = n-2，dp2[n-2] = nums[n-1]，对于 i = n-3，dp2[n-3] = nums[n-1] * nums[n-2]，依此类推。
4. 计算最终结果：
   • 对于每个索引 i，answer[i] = dp1[i] * dp2[i]，即是索引 i 位置的左右两边元素的乘积。

5.3 复杂度分析

时间复杂度

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们做了三次遍历：一次计算 dp1，一次计算 dp2，一次生成 answer。每次遍历的时间复杂度都是 O(n)。
• 空间复杂度：O(n)，我们使用了两个辅助数组 dp1 和 dp2，它们的空间复杂度为 O(n)，同时 answer 数组也占用 O(n) 空间。

5.4 改进（空间优化）

如果你希望优化空间复杂度，可以只使用一个数组 answer 来存储最终的结果，减少 dp1 和 dp2 的空间消耗。通过在一个数组上同时计算前缀积和后缀积，就可以做到空间复杂度为 O(1)，只是需要额外的常数空间。

5.4.1 示例代码：

优化后的代码（空间复杂度优化版）

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        
        // 初始化 answer 数组，默认值为 1
        vector<int> answer(n, 1);

        // 计算前缀积
        int left_product = 1;
        for (int i = 0; i < n; i++) {
            answer[i] = left_product;  // 设置当前元素为左侧所有元素的乘积
            left_product *= nums[i];   // 更新左侧乘积
        }

        // 计算后缀积并更新 answer 数组
        int right_product = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= right_product; // 更新为左右乘积
            right_product *= nums[i];   // 更新右侧乘积
        }

        return answer;
    }
};

5.4.2 时间复杂度和空间复杂度

• 时间复杂度：O(n)，仍然是三次遍历：一次计算前缀积，一次计算后缀积，最后生成结果。
• 空间复杂度：O(1)（不包括输入和输出数组）。我们只使用了 answer 数组作为额外的空间。

5.5 补充（可看可不看）

5.5.1 暴力解法

暴力解法的核心思想是：

1. 对于每个元素，计算该元素以外所有元素的乘积。
2. 计算的方式是嵌套遍历数组，对于每个元素，遍历一次剩余的元素并计算乘积。

暴力解法步骤

1. 遍历数组 nums 中的每个元素 nums[i]。
2. 对于每个 i，遍历剩余的数组元素，计算它们的乘积。
3. 最终将每个计算得到的乘积赋值给对应的 answer[i]。

5.5.2 示例代码：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n, 1);
        
        // 对于每个元素，计算它以外的所有元素的乘积
        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) {  // 不计算自己
                    product *= nums[j];
                }
            }
            answer[i] = product;  // 赋值到答案数组
        }
        
        return answer;
    }
};

5.5.2.1 代码解析

1. 外部循环：
   • for (int i = 0; i < n; i++)：遍历 nums 数组中的每个元素，i 表示当前要计算结果的元素的索引。
2. 内部循环：
   • for (int j = 0; j < n; j++)：遍历数组中的所有元素，对于每个元素 nums[j]，如果 i != j，则计算 nums[j] 的乘积。通过检查 i != j 来避免计算当前元素自身。
3. 计算乘积：
   • product *= nums[j]：逐个乘上其他元素，最后得到 i 位置元素以外的所有元素的乘积。
4. 赋值：
   • answer[i] = product：将计算出的乘积存入 answer[i]。

5.5.3 时间复杂度与空间复杂度

• 时间复杂度：
  • 外部循环遍历了 n 次，内部循环也遍历了 n 次。由于在每次外部循环中，我们都进行了 n-1 次计算，因此总的时间复杂度是 O(n^2)。
• 空间复杂度：
  • 我们使用了一个大小为 n 的 answer 数组来存储结果，因此空间复杂度为 O(n)。

5.5.4 改进方案

暴力解法虽然能解决问题，但它的时间复杂度是 O(n^2)，对于较大的数组来说效率较低。我们可以通过优化来减少时间复杂度，使用前缀积和后缀积的方法将时间复杂度降低到 O(n)，而空间复杂度优化到 O(1)（不算结果数组）。

优化方法思路如下：

优化后的方案就是在两次遍历中分别计算前缀积和后缀积，而不需要重复计算每个元素以外的乘积。

5.5.5 总结

• 暴力解法简单直观，但效率较低，时间复杂度为 O(n^2)。
• 如果数组长度较大，暴力解法可能不够高效，需要考虑优化方案，如使用前缀积和后缀积的 O(n) 解法。

5.6 总结

• 这个解法通过前缀积和后缀积两次遍历数组来构造最终的结果，空间复杂度和时间复杂度都非常优秀。
• 通过优化空间，减少了不必要的辅助数组，使得空间复杂度降低到 O(1)（不包括输出数组）。

6. 总结：

前缀和是一种高效的数组处理技巧，通过预处理阶段的 O(n) 时间，将区间求和等操作的复杂度降低到 O(1)，极大提升了算法效率。无论是在动态规划、数据查询，还是大数据分析等领域，前缀和都有广泛的应用，掌握它能够帮助我们更好地解决一些常见的算法问题。

7. 最后

通过上述「DP34 【模板】前缀和」、「【模板】二维前缀和」、「寻找数组的中心下标」及【除自身以外数组的乘积】等例子，可以总结出前缀和算法的核心思想、应用场景和优化技巧。 前缀和算法通过预先计算并存储部分数据，使得频繁的区间求和操作变得非常高效，时间复杂度从暴力解法的 O(n) 降低到 O(1)。在需要频繁进行区间查询的场景中，前缀和算法是一种非常有用的优化技巧，尤其适用于大数据量、高查询频率的应用。

路虽远，行则将至；事虽难，做则必成

亲爱的读者们，下一篇文章再会！！！