【算法一周目】从时光的边缘看世界：前缀和揭示的算法真谛

【算法一周目】从时光的边缘看世界：前缀和揭示的算法真谛

1.一维前缀和

题目链接： 【模板】一维前缀和

题目描述：

给定一个长度为 n 的整数数组 arr 和 q 个查询，每个查询由两个整数 l 和 r 组成，表示区间 [l, r]。请计算出每个区间内所有元素的和。

示例 1：

• 输入：arr = [1, 2,, 4, 5], q = 2, 查询区间为 [(1, ), (2, 4)]
• 输出：[6, 9]
• 解释：区间 [1, ] 的元素和为 1 + 2 + = 6，区间 [2, 4] 的元素和为 2 + + 4 = 9。

提示：

• 1 <= n, q <= 100000
• -10000 <= arr[i] <= 10000

---

解题思路 对于本道题，我们可以提前预处理出一个前缀和数组

dp

，通过前缀和数组快速求出某个区间所有元素的和。

前缀和数组

dp[i]

表示数组起始位置到第

i

个位置的所有元素和。其递推公式我们很容易得出：

dp[i] = dp[i-1] + arr[i]

计算区间

[l, r]

的所有元素的和：

sum = dp[r] - dp[l-1]

代码实现

代码语言：javascript代码运行次数：0运行复制

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

int main() {
    //处理输入输出
    int n, q;
    cin >> n >> q;
    vector<int> arr(n + 1);
    for(int i = 1; i <= n; ++i) cin >> arr[i];

    //预处理dp数组，long long元素类型防止溢出
    vector<long long> dp(n + 1);
    for(int i = 1; i <= n; ++i) dp[i] = dp[i - 1] + arr[i];

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

细节处理：我们开辟前缀和数组时开的空间大小应该比数组的大1（开辟

n + 1

的空间），可以让数组的元素位置与下标一一对应（第一个元素对应下标1位置），帮助我们规避掉像

dp[1]

等边界情况。

---

2.二维前缀和

题目链接：【模板】二维前缀和

题目描述：

给定一个大小为 n × m 的矩阵 matrix 和 q 个查询，每个查询由四个整数 x1, y1, x2, y2 组成，表示一个子矩阵的左上角 (x1, y1) 和右下角 (x2, y2)。请计算出每个子矩阵内所有元素的和。

示例 1：

• 输入：matrix = [[1, 2], [, 4]], q = 1, 查询区间为 [(1, 1, 2, 2)]
• 输出：[10]
• 解释：子矩阵包含所有元素 1 + 2 + + 4 = 10。

提示：

• 1 <= n, m <= 1000
• -10000 <= matrix[i][j] <= 10000

---

解题思路

这道题与上一道题类似，我们可以提前预处理出一个前缀矩阵和数组

dp

，

dp[i][j]

表示矩阵从

[1, 1]

位置到

[i, j]

位置的所有元素和，然后利用

dp

数组快速求出子矩阵内所有元素的和。

1. 构建前缀和矩阵数组
   • 构建数组时与上题类似，每一行每一列多开一个空间以此来避免边界情况。

   在这里插入图片描述

   • 递推公式：

   dp[i][j] = matrix[i][j] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]

2. 计算

[x1. y1] -> [x2, y2]

任意子矩阵的和

sum

在这里插入图片描述

sum = dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]

代码实现

代码语言：javascript代码运行次数：0运行复制

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

int main() {
    //处理输入数据
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> vv(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
            cin >> vv[i][j];
    }

    //预处理矩阵数组, longlong防溢出  
    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] + vv[i][j] - dp[i - 1][j - 1];
    }

    //输出
    int x1, y1, x2, y2;
    while(q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        long long ret = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
        cout << ret << endl;
    }

    return 0;
}

---

.寻数组的中心下标

题目链接：724. 寻数组的中⼼下标

题目描述：

给你⼀个整数数组 nums ，请计算数组的 中心下标 。

中心下标是数组的⼀个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0，因为在下标的左侧不存在元素。这⼀点对中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那⼀个。如果数组不存在中心下标，返回 -1。

示例 1：

• 输入：nums = [1, 7, , 6, 5, 6]
• 输出：
• 解释：
  • 中心下标是 。
  • 左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + = 11 ，
  • 右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，⼆者相等。

示例 2：

• 输入：nums = [1, 2, ]
• 输出：-1
• 解释：
  • 数组中不存在满足此条件的中心下标。

示例 ：

• 输入：nums = [2, 1, -1]
• 输出：0
• 解释：
  • 中心下标是 0。
  • 左侧数之和 sum = 0，（下标 0 左侧不存在元素），
  • 右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0。

提示：

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

---

解题思路 根据题目要求，我们可以预处理出一个前缀和数组

f

和后缀和数组

g

，然后遍历数组通过比较前缀和和后缀和到中心下标。

1. 前缀和数组

   f[i]

   表示数组开始位置到

   i-1

   位置的所有元素和

   • 递推公式：

   f[i] = f[i-1]+nums[i-1]

2. 后缀和数组

   g[i]

   表示数组

   i+1

   位置到数组末尾位置的所有元素和

   • 递推公式：

   g[i] = g[i+1]+nums[i+1]

代码实现

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        //预处理出前缀和、后缀和数组
        int n = nums.size();
        vector<int> f(n);
        //数组起始位置的左侧
        for(int i = 1; i < n; ++i)
            f[i] = f[i - 1] + nums[i - 1];
        
        vector<int> g(n);
        for(int i = n - 2; i >= 0; --i)
            g[i] = g[i + 1] + nums[i + 1];
        
        //遍历数组到中心下标
        for(int i = 0; i < n; ++i)
        {    if(f[i] == g[i])
                return i;
        }
        return -1;
    }
};

优化解法

上面的解法其实还可以优化，设

nums

的所有元素之和为

S

，中心下标为

i

，

i

左边的元素和为

lsum

，根据左侧元素和与右侧元素和相等有：

lsum = S-nums[i]-lsum

稍微化简有：

2\times lsum = S-nums[i]

所以我们只需用一个量

leftsum

记录当前元素的左侧元素和，根据推导公式判断当前位置是否为中心下标。

优化后的解法时间复杂度从

O(n)

降到了

O(1)

了。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = 0;
        for(auto e : nums)
            sum += e;
        
        int leftSum = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(2 * leftSum == sum - nums[i])
                return i;
            
            leftSum += nums[i];
        }
        return -1;
    }
};

---

4.除自身以外数组的乘积

题目链接：28. 除自身以外数组的乘积

题目描述：

给你⼀个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题⽬数据保证数组 nums 中任意元素的全部前缀元素和后缀的乘积都在 2 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1：

• 输入：nums = [1, 2, , 4]
• 输出：[24, 12, 8, 6]

示例 2：

• 输入：nums = [-1, 1, 0, -, ]
• 输出：[0, 0, 9, 0, 0]

提示：

• 2 <= nums.length <= 105
• -0 <= nums[i] <= 0
• 保证数组 nums 中任意元素的全部前缀元素和后缀的乘积都在 2 位整数范围内。

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

---

解题思路

与上一题类似，我么先预处理出前缀积数组

f

和后缀积数组

g

，然后将两者相乘得到除自身元素以外的乘积。

1. 前缀积数组

f[i]

表示数组起始位置到第

i-1

位置所有元素的积。

• 递推公式：

f[i]=f[i-1] \times nums[i-1]

1. 后缀积数组

g[i]

表示数组第

i+1

位置到数组末尾位置所有元素的积。

• 递推公式：

g[i]=g[i+1] \times nums[i+1]

细节：

f[0] = g[n-1]=1

，对于这两个数组初始情况需要为1

构建出前缀积与后缀积数组后，我们直接遍历，两者相乘，构建出需要返回的数组

ret

代码实现

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n,1);
        for(int i = 1; i < n; ++i)
            f[i] = f[i - 1] * nums[i - 1];

        vector<int> g(n,1);
        for(int i = n - 2; i >= 0; --i)
            g[i] = g[i + 1] * nums[i + 1];
        
        vector<int> ret;
        for(int i = 0; i < n; ++i)
            ret.push_back(f[i] * g[i]);
        
        return ret;
    }
};

优化解法

我们可以先处理出后缀积

g

，用 pre 记录前缀积（初始化为1），然后遍历将

pre

乘到

g[i]

中，同时维护

pre

，最后将 g 返回即可。

这种写法相较于上种可以少遍历一次数组，而且题目说到输出数组不被视为额外空间，故时间复杂度为

O(1)

。

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> g(n,1);
        //后缀积
        for(int i = n - 2; i >= 0; --i)
            g[i] = g[i + 1] * nums[i + 1];
        
        //遍历修改g[i]
        //pre为i位置左侧元素的乘积
        int pre = 1;
        for(int i = 0; i < n; ++i)
        {
            
            g[i] *= pre;
            pre *= nums[i];
        }
        
        return g;
    }
};

---

5.和为k的子数组

题目链接：560. 和为 K 的子数组

题目描述：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

示例 1：

• 输入：nums = [1,1,1], k = 2
• 输出：2
• 解释：共有两个子数组的和为 2，分别是 [1,1] 和 [1,1]。

示例 2：

• 输入：nums = [1,2,], k =
• 输出：2
• 解释：共有两个子数组的和为 ，分别是 [1,2] 和 []。

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

---

解题思路

根据题目要求，我们需要求出和为

K

的子数组的个数。

我们可以使用暴力解法，定义两个指针

i

和

j

，固定

i

，

j

依次往后遍历，注意，到符合的数组后，

j

也要继续遍历，因为以

i

为起点的和为

K

的子数组不止一个，

j

遍历完一遍数组后

i

往后加一，直到

i

遍历完数组，这样就求出和为

K

的子数组的个数，但是暴力解法的时间复杂度是

O(n^2)

，一定会超时。

对于这道题，我们不能使用滑动窗口，当窗口内出现符合的子数组时，统计个数后窗口的左边端点会前移，因为数组的元素有正有负不满足单调性，这样是会错过一些符合的数组，比如在

[1, -1, 0, 0, 0]

求和为

0

的子数组的个数。

我们的最优解法是前缀和+哈希表。对于

[0, i]

区间的数组，其元素之和为

sum

，如果通过哈希表查询到该区间数组和为

sum - K

的子数组的个数，这样就间接知道了

[0, i]

区间的数组内和为 K 的子数组的个数。

在这里插入图片描述

代码实现

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //哈希表记录前缀和及其出现的次数
        unordered_map<int, int> hash;
        //处理区间和为K的特殊情况
        hash[0] = 1;

        int sum = 0, ret = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            //计算[0,i]的前缀和
            sum += nums[i];
            //查和为sum-k的子数组的个数
            if((sum - k)) ret += hash[sum-k];
            //将前缀和加入哈希表
            hash[sum]++;
        }
        return ret;
    }
};

细节处理：

1. 对于前缀和，我们没有必要格外开辟空间来计算，只需要用一个变量

sum

去维护即可。

hash[0]=1

：和为 0 的子数组出现的次数默认有一次，这是因为区间元素和刚好第一次为

K

时，按照我们的算法，需要查和为

0

的子数组个数，但是由于整个区间的所有元素和为

K

，没有额外剩余的元素去构成和为

0

的子数组，所以如果没有

hash[0]=1

，哈希表是查不到和为

0

的子数组的个数，我们的算法是会遗漏整个区间的和第一次为

K

的情况，最后统计出来的和为

K

的子数组的个数是会少一个的。

• 时间复杂度：

O(n)

• 空间复杂度：

O(n)

，哈希表的空间开销

---

6.和可被k整除的子数组

题目链接：974. 和可被 K 整除的子数组

题目描述：

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空）子数组的数目。

示例 1：

• 输入：nums = [4,5,0,-2,-,1], k = 5
• 输出：7
• 解释：共有 7 个子数组满足其元素之和可被 k = 5 整除： [4, 5, 0, -2, -, 1], [5], [5, 0], [5, 0, -2, -], [0], [0, -2, -], [-2, -]

示例 2：

• 输入：nums = [5], k = 9
• 输出：0

提示：

• 1 <= nums.length <= * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 10^4

---

解题思路

对于这道题，我们依然使用前缀和+哈希表，但是在此之前先引入下同余定理。

同余定理：

• 如果

(a-b) \bmod K = = 0

，则有

a \bmod K == b \bmod K

。

所以整体思路就是对于

[0, i]

区间的数组，其元素之和为

sum

，对

sum

进行取模(

\bmod K

)余数为

mod

，如果通过哈希表查询到该区间内数组和的余数同样为

mod

的子数组的个数，这样就间接知道了

[0, i]

区间的数组内和可为 K 整除的子数组的个数。

在这里插入图片描述

代码实现

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        //哈希表存储前缀和余数及其出现的次数
        unordered_map<int, int> hash;
        //处理区间元素和刚好被K整除，余数为0的特殊情况
        hash[0] = 1;

        int ret = 0, sum = 0;
        for(auto e : nums)
        {
            //计算前缀和
            sum += e;
            //对前缀和取模，注意在C++中，余数可为负
            //需要换算成非负以免影响结果
            int mod = (sum % k + k) % k;
            //查前缀和的余数为mod的子数组的个数
            if((mod))
                ret += hash[mod];
            //将余数加入哈希表
            hash[mod]++;
        }
        return ret;
    }
};

代码解析：

1. 哈希表存储的是前缀和的余数及其出现的次数，与上道题不同。

hash[0] = 1

：余数为

0

默认出现次数为

1

次，是为了处理区间元素和第一次刚好被

K

整除的特殊情况，防止答案遗漏。

1. (sum % k + k) % k ：在C++中，余数可以为负数，需要将其调整为正数，不然会影响结果。

• 时间复杂度：

O(n)

• 空间复杂度：

O(K)

，哈希表存储余数的额外空间开销。

---

7.连续数组

题目链接：525. 连续数组

题目描述：

给定一个二进制数组 nums，到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1：

• 输入：nums = [0,1]
• 输出：2
• 说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2：

• 输入：nums = [0,1,0]
• 输出：2
• 说明：[0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1

---

解题思路

题目要求我们含有相同数量的

0

和

1

的最长连续子数组的长度，我们可以将0看作成-1，这样问题就转换成了求和为0的子数组最长长度。

解决这道题的思路依然是前缀和+哈希，对于

[0, i]

区间的数组，其元素之和为

sum

，通过哈希表查询到该区间内数组和同样为

sum

的子数组的末尾元素下标，间接求出和为

0

的子数组长度。

但是需要注意的是，当哈希表中已经存在

sum

时，不必更新

sum

在哈表中的下标，因为题目要求的是子数组最长长度。

在这里插入图片描述

代码实现

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        //哈希表存储的是[0,i]区间元素和及其下标i
        unordered_map<int, int> hash;
        //处理前缀和刚好为0的情况
        hash[0] = -1;

        int sum = 0, ret = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            //将数组中的0看待成-1
            sum += nums[i] == 0 ? -1 : 1;
            //如果前缀和存在则更新结果，不存在再加入哈希表
            if((sum)) ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }
        return ret;
    }
};

代码解析：

1. 哈希表存储

[0,i]

区间元素和及其下标

i

。

hash[0] = -1

：前缀和为

0

的子数组下标默认为

-14

， 处理处理前缀和第一次为

0

的特殊情况。

• 时间复杂度：

O(n)

• 空间复杂度：

O(n)

，哈希表的额外空间开销。

---

8.矩阵区域和

题目链接：14. 矩阵区域和

题目描述：

给你一个 m x n 的矩阵 mat 和一个整数 k，请你返回一个矩阵 answer，其中每个 answer[i][j] 是所有满足以下条件的元素 mat[r][c] 的和：

• i - k <= r <= i + k
• j - k <= c <= j + k
• (r, c) 在矩阵内。

示例 1：

• 输入：mat = [[1,2,],[4,5,6],[7,8,9]], k = 1
• 输出：[[12,21,16],[27,45,],[24,9,28]]

示例 2：

• 输入：mat = [[1,2,],[4,5,6],[7,8,9]], k = 2
• 输出：[[45,45,45],[45,45,45],[45,45,45]]

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n, k <= 100
• 1 <= mat[i][j] <= 100

---

解题思路

通过分析题目可以知道，其实就是快速求出子矩阵

[i-k, j-k]

到

[i+k, j+k]

的所有元素的和，我们可以先预处理出来一个矩阵前缀和数组

dp

，然后通过矩阵前缀和数组快速求出子矩阵的所有元素和。

1. 构建矩阵前缀和

dp

1. 通过

dp

快速求子矩阵的和

• 由于矩阵前缀和的下标与矩阵

mat

并不是一一对应的，我们在计算子矩阵的起始位置与末尾位置的下标时要进行转换。

• 根据题目可知，我们通过

i

和

j

求子矩阵的坐标时是可能会越界，我们要特殊处理。

sum = dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]

代码实现

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        //1.初始化前缀和数组，需要多加一行多加一列
        int m = mat.size(), n = mat[0].size();
        //dp[i][j]代表矩阵mat从[0][0]到[i-1][j-1]的所有元素的和
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i < m + 1; ++i)
            for(int j = 1; j < n + 1; ++j)
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
        
        //2.使用前缀和数组求和
        vector<vector<int>> ret(m, vector<int>(n));
        for(int i = 0; i < m; ++i)
        {
            //下标转换并且要进行越界情况的处理
            int x1 = max(0, i - k) + 1;
            int x2 = min(m - 1, i + k) + 1;
            for(int j = 0; j < n; ++j)
            {
                int y1 = max(0, j - k) + 1;
                int y2 = min(n - 1, j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            }
        }
        return ret;
    }
};

代码解析：

1. 矩阵前缀和

dp

与矩阵

mat

的下标不是一一对应的，比如

dp[1][1]

对应原数组

mat[0][0]

，计算矩阵前缀和要留意。

1. 通过

i

与

j

求子矩阵的坐标时要防止越界并且转换成与

dp

数组对应，因为要通过

dp

求出子矩阵的所有元素和。

• 时间复杂度：

O(m \times n)

• 空间复杂度：

O(m \times n)

，矩阵前缀和数组

dp

的额外空间开销

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-12-28，如有侵权请联系 cloudcommunity@tencent 删除前往查看遍历数组算法dpint