1.簡(jiǎn)介

前綴和算法是一種用空間換時(shí)間的算法，他常常用于解決某些題目或者作為某些高級(jí)算法的組成部分。

例如：讓你求某個(gè)矩陣（一維）的子矩陣的最大值，如果使用暴力解法它的時(shí)間復(fù)雜度將會(huì)是O(n^2) ，但如果使用該算法就可以使其時(shí)間復(fù)雜度降低一個(gè)維度也就是O(N).

2.一維前綴和

講解

該算法需要開辟一個(gè)比原數(shù)組的大小大一個(gè)內(nèi)存的數(shù)組

它的每一個(gè)元素意義是：前原數(shù)組n個(gè)元素的總和。也就是說下標(biāo)為3的元素，是原來前三個(gè)元素的和。（也可以理解為除了自己以外的前面元素的和）

至于為什么會(huì)多開辟一個(gè)元素，我們后續(xù)會(huì)講。

因此我們可以得出求和數(shù)組的遞推公式：

$sum[i]=arr[i?1]+sum[i?1]$

此時(shí)我們多開一個(gè)內(nèi)存的意義就可以體現(xiàn)出來了，當(dāng)我們求第一個(gè)元素?cái)?shù)組的時(shí)候需要加上前一個(gè)sum 。

但是如果第一個(gè)元素前一個(gè)位置沒有東西就會(huì)發(fā)生越界訪問，因此我們要給他提前準(zhǔn)備一個(gè)內(nèi)存并且默認(rèn)為0。

總的來說，就是為了處理第一個(gè)元素越界的問題。

求子矩陣內(nèi)的和

我們已經(jīng)知道了sum的每一個(gè)元素的意義，那么原數(shù)組的子矩陣的和也就可以得出來，例如：下標(biāo)x到y(tǒng)的子矩陣之和就等于：

$son=sum[y+1]?sum[x]$

代碼

如果你理解了上述內(nèi)容，它的代碼就可以輕松寫出來：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int arr[5] = {1,2,3,4,5};
	int sum[6];
	sum[0] = 0;

	for (int i = 1; i < 6; i++) sum[i] = arr[i - 1] + sum[i - 1];

	for (auto i : sum) cout << i << ' ';
	
	return 0;
}

運(yùn)行結(jié)果：

3.二維前綴和

講解

二維前綴和相對(duì)于一維復(fù)雜的多，它也需要多開辟空間，不同的是他是在每個(gè)維度都要多開辟一個(gè)。

它每個(gè)元素的意義是：下標(biāo)為(x,y)的求和數(shù)組的元素，是原數(shù)組下標(biāo)（0,0）到（x - 1, y - 1）子矩陣內(nèi)元素的和，建議配合圖來理解。

舉個(gè)例子： sum[2][2] = arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1] 其他也是如此。

如果你理解了上述內(nèi)容，那么就讓我們來推一下它的遞推公式：
至于我們?yōu)槭裁匆@么求，暫且往下看。

當(dāng)我們求前綴和的時(shí)候，我們是順序求取的，當(dāng)我們求（x，y）位置的前綴和時(shí)候，我們的（x,y - 1），(x - 1, y -1)，(x- 1,y)這三個(gè)位置的前綴和就已經(jīng)求出來了，也就是說ABCD的位置的值你都是知道的，所以我們我么可以得出以下公式：

$sum[x][y]=sum[x?1][y]+sum[x][y?1]?sum[x?1][y?1]+arr[x?1][y?1]$

求子矩陣和

求子矩陣和是建立在已經(jīng)求出所有前綴和基礎(chǔ)上的，求子矩陣和的方法和求前綴和的方法相似，且看圖解：

由此我們可以得出遞推公式，原數(shù)組（x1,y1）到（x,y）的子矩陣：
$son=sum[x+1][y+1]+sum[x1][y1]?sum[x+1][y1]?sum[x1][y+1]$

代碼

#include<bits/stdc++.h>
using namespace std;
int main()
{
	vector<vector<int>>v(3, vector<int>(3));
	vector<vector<int>>sum(4, vector<int>(4, 0));

	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
		{
			v[i][j] = j + 1;//每個(gè)一維數(shù)組初始化為1 2 3
			sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + v[i][j];//遞推
		}
	
	for (auto i : sum)
	{
		for (auto k : i)
			cout << k << ' ';
		cout << endl;
	}

	int x1, y1,x,y;

	cout << "子矩陣坐標(biāo)：" << endl;
	cin >> x1 >> y1 >> x >> y;//求子矩陣
	cout << sum[x + 1][y + 1] - sum[x + 1][y1] - sum[x1][y + 1] + sum[x1][y1];

	return 0;
}

運(yùn)行結(jié)果：

4.題目

一維前綴和模板

點(diǎn)這里進(jìn)入
答案：最簡(jiǎn)單的都不會(huì)？？？回去再翻翻去

二維前綴和模板

點(diǎn)這里進(jìn)入
答案：這個(gè)做對(duì)了說明你理解這個(gè)算法了

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;

    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
    vector<vector<int>> dp(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];
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
        }
    }
    int x1, y1, x2, y2;
    while (q--) {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] <<
             endl;
    }
    return 0;
}

尋找數(shù)組的中心下標(biāo)

點(diǎn)吧你，一點(diǎn)一個(gè)不吱聲

思路：

1. 前綴和+后綴和（這個(gè)純屬就是前綴的倒序版）
2. 如果這個(gè)元素的前綴和和后綴和相同，說明找到了。

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

        vector<int>dp(nums.size() + 1, 0);
        vector<int>dp1(nums.size() + 1, 0);

        for (int i = 1; i <= nums.size(); i++) {
            dp[i] = dp[i - 1] + nums[i - 1];
        }
        for(int i = nums.size() - 2; i >= 0; i--){
            dp1[i] = dp1[i + 1] + nums[i + 1];
        }

        for (int i = 0; i < nums.size(); i++) {
            if (dp[i] == dp1[i])
                return i;
        }

        return -1;
    }
};

除自己以外數(shù)組的乘積

點(diǎn)我就完事了
思路：

1. 前綴和算法的簡(jiǎn)單變化，本質(zhì)依舊如此
2. 可以使用上一個(gè)題的方法，前綴和+后綴和
3. 下面的方法是那個(gè)方法的優(yōu)化，空間復(fù)雜度優(yōu)化到了O(1)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
       // int sum = accumulate(nums.begin(), nums.end(), 1, mulltiplies<int>());
        int n = nums.size();
        vector<int> ans(n);
        ans[0] = 1;

        for(int i = 1; i < n;i++)
            ans[i] = ans[i - 1] * nums[i - 1];
        
        int r = 1;
        for(int i = n - 1; i >= 0;i--){
            ans[i] = ans[i] * r;
            r *= nums[i];
        }

        return ans;
    }
};

和為k的子數(shù)組

挺難的
思路：

1. 假設(shè)這個(gè)位置存在連續(xù)數(shù)組使其和為target，那么說明其前面的前綴和必存在sum - target的值
2. 配合哈希表使用，記錄前面每個(gè)前綴和出現(xiàn)的次數(shù)
3. 從頭開始遍歷，一遍存前綴和，一邊找是否有符合的數(shù)組

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        int sum = 0;
        int ret = 0;

        for(auto i : nums)
        {
            hash[sum]++;
            sum += i;
            if(hash.count(sum - k)) ret += hash[sum - k];
        }
        return ret;
    }
};

感謝觀眾老爺?shù)挠^看Thanks?(?ω?)?，如果覺得滿意的話留個(gè)關(guān)注再走吧。文章來源地址http://www.zghlxwxcb.cn/news/detail-850044.html

到了這里，關(guān)于【算法精講】一篇讓你掌握前綴和算法（附圖解和不少題目練習(xí)~~）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！