Offer必备算法_前缀和_牛客+力扣OJ题详解（由易到难）

先预处理出来⼀个前缀和数组：用 dp[i] 表表示：[1, i] 区间内所有元素的和（注意从1开始，dp[0]给0就行），那么 dp[i - 1] 里面存的就是 [1, i - 1] 区间内所有元素的和，那么：可得递推公式： dp[i] = dp[i - 1] + arr[i] ；
使用前缀和数组，快速求出某⼀个区间内所有元素的和：当询问的区间是 [left , right] 时：区间内所有元素的和为： dp[right] - dp[left - 1] 。

前缀和算法的主要优势在于它可以用较低的时间复杂度O（N）计算指定范围内的元素和，而不是每次都需要重新遍历计算。

以下是一个示例，演示如何使用前缀和算法计算数组的前缀和：

原始数组: [1, 2, 3, 4, 5]，其前缀和数组: [1, 3, 6, 10, 15]

解释：原始数组的前缀和：[1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5] = [1, 3, 6, 10, 15]

二维前缀和

在一维数组前缀和算法的基础上，想到：计算二维数组前缀和，不就和计算一维数组前缀和一样，即计算每一个位置的前缀和就相当于：

此位置的前缀和 = 这个位置的值 + 此位置前的前缀和

Eg：s[3][1] = a[0][0] + a[0][1] + a[0][2] + a[0][3] +a[1][1] + a[1][2] + …… + a[3][1]

但事实真的是这样吗？其实不是的，如果按照上述的方式去计算二维数组前缀和的话，本质其实就相当于遍历了一次二维数组，其时间复杂度就为O(N*M)了，其实已经偏离了前缀和的本心了

所以，在这里我们计算前缀和采取了另外一种计算策略：拼接

简单来说，就是遵循：计算哪个点的前缀和，就以这个点的横纵左边为边界，计算此点与起点（[1，1]）之间所形成的矩阵内所有元素的和的原则。

简单图解：这里把矩阵的最上面和最左边添加上一行和一列 0，这样可以省去很多的边界处理。

预处理出二维前缀和数组：

使用二维前缀和数组：

综上，便可以得出两条递推公式

计算某一个位置的前缀和：

dp[i, j] = 第i行j列格子与起点（[1,1]）所围成的矩阵中所有元素的和

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

计算某一区间的前缀和

以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：

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

①牛客DP34 【模板】前缀和

【模板】前缀和_牛客题霸_牛客网

#include <iostream>
using namespace std;

int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        cout << a + b << endl;
    }
}
// 64 位输出请用 printf("%lld")

解析代码

暴力解法就是模拟（模拟题目意思），q次询问就遍历数组q次，这样时间复杂度是O（N^2），使用前缀和算法只需遍历一遍数组处理出前缀和数组，询问的时候O（1）就能询问了，时间复杂度是O（N）。

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

int main() 
{
    int n = 0, q = 0;
    cin >> n >> q;
    vector<int> arr(n + 1, 0);
    for (int i = 1; i <= n; i++) // 读取数据
    {
        cin >> arr[i];
    }
    vector<long long> dp(n + 1, 0); // 防溢出
    for (int i = 1; i <= n; i++) // 处理前缀和数组
    {
        dp[i] = dp[i - 1] + arr[i];
    }
    int left = 0, right = 0;
    while (q--) // 计算区间和
    {
        cin >> left >> right;
        cout << dp[right] - dp[left - 1]<< endl;
    }
    return 0;
}

②牛客DP35 【模板】二维前缀和

【模板】二维前缀和_牛客题霸_牛客网

#include <iostream>
using namespace std;

int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        cout << a + b << endl;
    }
}
// 64 位输出请用 printf("%lld")

解析代码

想到高中数学的一句话：手中无图，心中有图。想着图敲上面的公式就行了。

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

int main() 
{
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> arr(n + 1, vector<int>(m + 1, 0));
    for(int i = 1; i <= n; ++i) // 读数据
    {
        for(int j = 1; j <= m; ++j)
        {
            cin >> arr[i][j]; 
        }
    }
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    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] + arr[i][j] - dp[i-1][j-1];
        }
    }
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    while(q--) // 使用前缀和数组查询
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] << endl;
    }
    return 0;
}

③力扣724. 寻找数组的中心下标

724. 寻找数组的中心下标

LCR 012. 寻找数组的中心下标

1991. 找到数组的中间位置（三道一样的题，一鱼三吃）

难度简单

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000

class Solution {
public:
    int pivotIndex(vector<int>& nums) {

    }
};

解析代码

暴力法是时间复杂度O(N^2)，用前缀和思想是O(N)，构造一个前缀和数组arr1和一个后缀和数组arr2，然后遍历比较。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        // 暴力法是时间复杂度O(N^2)，用前缀和思想是O(N)
        // 构造一个前缀和数组arr1和一个后缀和数组arr2，然后遍历比较
        int n = nums.size();
        vector<int> arr1(n, 0), arr2(n, 0);
        for(int left = 1, right = n-2; left < n; ++left, --right)
        {
            arr1[left] = arr1[left-1] + nums[left-1]; // arr1表示其左边的和，所以nums[left-1]
            arr2[right] = arr2[right+1] + nums[right+1]; // 构成后缀和
        }
        for(int i = 0; i < n; ++i)
        {
            if(arr1[i] == arr2[i])
            {
                return i;
            }
        }
        return -1;
    }
};

④力扣238. 除自身以外数组的乘积

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

难度中等

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

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

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

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

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

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {

    }
};

解析代码

题目的提示就差直接告诉你用前缀和思想了，类似力扣724的代码：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr1(n, 1), arr2(n, 1), ret(n);
        for(int left = 1, right = n-2; left < n; ++left, --right)
        {
            arr1[left] = arr1[left-1] * nums[left-1]; // 前缀积
            arr2[right] = arr2[right+1] * nums[right+1]; // 后缀积
        }
        for(int i = 0; i < n; ++i)
        {
            ret[i] = arr1[i] * arr2[i];
        }
        return ret;
    }
};

⑤力扣560. 和为 K 的子数组

560. 和为 K 的子数组

难度中等

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

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

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

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {

    }
};

解析代码

使用前缀和的方法解决这个问题，因为需要找到和为k的连续子数组的个数。

通过计算前缀和，可以将问题转化为求解两个前缀和之差等于k的情况。

假设数组的前缀和数组为arr，其中arr[i]表示从数组起始位置到第i个位置的元素之和。

那么对于任意的两个下标i和j（i < j），如果arr[j] - arr[i] = k，即从第i个位置到第j个位置的元素之和等于k，那么说明从第i+1个位置到第j个位置的连续子数组的和为k。 通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。

在遍历的过程中，检查是否存在arr[j] - k的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为k，将对应的次数累加到结果中。

这样，通过遍历一次数组，就可以统计出和为k的连续子数组的个数，时间复杂度为O（N）。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 根据前缀和思想，设一个位置前缀和为sum，sum-前缀和 == k的区间即为所求
        // 利用哈希求有多少个 sum-前缀和 == k的区间
        int n = nums.size(), sum = 0, ret = 0;;
        unordered_map<int, int> hash(n); // 左int存前缀和，右int存前缀和出现次数
        hash[0] = 1; // 初始化前缀和为0的次数为1（整个数组等于K的情况）
        for(int i = 0; i < n; ++i)
        {
            sum += nums[i]; // 计算i位置的前缀和
            if(hash[sum - k] != 0) // 判断i位置前缀和-k是否存在
            {
                ret += hash[sum - k];
            }
            hash[sum]++; // 计算i之前只保存i-1
        }
        return ret;
    }
};

⑥力扣974. 和可被 K 整除的子数组

974. 和可被 K 整除的子数组

难度中等

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

子数组 是数组的连续部分。

示例 1：

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

示例 2:

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

提示:

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

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {

    }
};

解析代码

和上一题力扣560. 和为 K 的子数组的原理一样，只是要多了解两个知识：

①同余定理。②C++对负数取模的修正。

同余定理：数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系（即a % m == b % m）。

数学中的取余法则，即两个数取余，余数总是为正数。

C++/Java中负数对正数取余的结果是负数，所以要修正：

C++取模：当被除数为负数时取模结果为负数，需要纠正 -> (x % k + k) % k;

如C++中 -10 % 7 = -3（-10 + 7 * 1 = 3），而数学中 -10 % 7 = 4（-10 + 7 * 2 = 4）

所以在C++中要手动修正成-> （-10 % 7 + 7）% 7 = 4。

理解上面两个知识之后代码就和上一题力扣560. 和为 K 的子数组的差不多一样了：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int n = nums.size(), sum = 0, ret = 0;;
        unordered_map<int, int> hash(n); // 左存前缀和对k取模的余数，右存前缀和出现次数
        hash[0 % k] = 1;
        for(int i = 0; i < n; ++i)
        {
            sum += nums[i];
            int remainder = (sum % k + k) % k;
            if(hash[remainder] != 0)
            {
                ret += hash[remainder];
            }
            hash[remainder]++;
        }
        return ret;
    }
};

⑦力扣525. 连续数组

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 <= 10^5
nums[i] 不是 0 就是 1

class Solution {
public:
    int findMaxLength(vector<int>& nums) {

    }
};

解析代码

把数组的0变成/当成-1之后，就转化成力扣560. 和为 K 的子数组了（此时K=0）

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        // 转化成找一段和为0的最长子数组 -> 把数组的0变成/当成-1
        int sum = 0, n = nums.size(), ret = 0;
        unordered_map<int, int> hash(n); // 左存前缀和，右存下标
        hash[0] = -1; // 默认有一个前缀和为0的情况，下标为-1，如[0,1]返回就是1 - (-1) = 2
        for(int i = 0; i < n; ++i)
        {
            sum += nums[i] == 0 ? -1 : 1;
            if(hash.count(sum)) // 找最左面有没有前缀和和此时一样的
            {
                ret = max(ret, i - hash[sum]); // 找到前面出现一样的，则那个位置到现在的位置和为0
            }
            else // 前面没有一样的才更新，保证最左边
            {
                hash[sum] = i; 
            }
        }
        return ret;
    }
};

⑧力扣1314. 矩阵区域和

1314. 矩阵区域和

难度中等

给你一个 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,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

输入：mat = [[1,2,3],[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

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {

    }
};

解析代码

题意有点类似C语言写过的三子棋的一个功能？要返回的二维数组就是原数组上下左右移动K的单位包起来的正方形区域所有元素的和（越界的不管），用二维前缀和解决。

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j) // 此题的mat下标不是从1开始的，注意转化
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
        
        vector<vector<int>> ret(m, vector<int>(n));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                int x1 = max(0, i - k) + 1; // 左上角
                int y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + 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;   
    }
};