博客主頁:酷酷學!!!
感謝關(guān)注~

---

1. 前綴和

算法思路:

根據(jù)題意, 創(chuàng)建一個前綴和數(shù)組, dp[i] = dp[i -1] + arr[i], 再使用前綴和數(shù)組, 要求的區(qū)域ret = dp[r] - dp[l-1], 這里我們?yōu)槭裁匆@樣求dp[i]呢? 還要繞一大圈子, 直接相加不就行了 , 但是如果直接相加求還不如我們的暴力解法呢, 這里還要開辟空間, 但是我們使用dp[i]求解只需遍歷一遍數(shù)組即可求出前綴和

需要注意:

1. 創(chuàng)建前綴和數(shù)組默認從0開始, 如果我們從1開始訪問則需要先將數(shù)組初始化好,
2. 因為dp[i] 的大小可能超過int所以需要創(chuàng)建long long類型的數(shù)組.

編寫代碼:

#include <iostream>
#include <vector>
using namespace std;int main() 
{int n = 0, q = 0;cin>>n>>q;vector<long long> dp(n+1,0);int num = 0;for(int i = 1; i <= n; i++){cin>>num;dp[i] = dp[i-1] + num;}while(q--){int l,r;cin>>l>>r;cout<<dp[r] - dp[l-1]<<endl;}return 0;
}
// 64 位輸出請用 printf("%lld")

---

2. 二維前綴和

算法思路:

分析題意, 很顯然如果我們使用暴力解法一定會超時的.
首先分析題目, 我們可以先預處理出來一個前綴和矩陣如下圖所示, 求出每一個dp[i][j]

然后我們使用dp[i][j],根據(jù)所求的區(qū)域我們就可以找出一個求出結(jié)果的公式, 于是我們就可以搞出來一個時間復雜度為O(N)的算法,當然空間復雜度也為O(N).

編寫代碼:

#include<iostream>
#include<vector>
using namespace std;
int main()
{   int n,m,q;cin>>n>>m>>q;vector<vector<int>> arr(n+1,vector<int>(m+1));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));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] - dp[i-1][j-1] + arr[i][j];}}int x1,y1,x2,y2;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;
}

---

3. 尋找數(shù)組的中心下標

算法思路1:

分析題意, 發(fā)現(xiàn)可以使用前綴和來解決, 首先預處理出來一個前綴和數(shù)組, 然后我們只需在遍歷一遍前綴和數(shù)組, 只要找到一個位置前面的區(qū)域和后面的區(qū)域相同, 則就找到了該位置, 但是注意我們的dp是從1開始的所以返回結(jié)果需要-1, 如果沒有找到返回-1即可, 注意預處理前綴和數(shù)組的時候與原數(shù)組的映射關(guān)系.

編寫代碼:

class Solution {
public:int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int> dp(n+1,0);for(int i = 1; i <= n ;i++){dp[i] = dp[i-1] + nums[i-1];}for(int i = 1; i <= n ;i++){if(dp[i-1] == (dp[n] - dp[i]))return i-1;}return -1;}
};

算法思路二:

既然我要算左邊和右邊的和是否相等, 那么我們不妨弄兩個的dp數(shù)組, 一個前綴和一個后綴和, 對于前綴和我們只需要求出i之前的所有元素之和即可, 對于后綴和我們只需要求出i位置之后的所有元素之和即可, 但是注意細節(jié)我們需要考慮第一次計算會訪問越界的情況, 所以我們需要提前把f[0]和g[n-1]這個位置處理好,而vector默認就為0.

編寫代碼:

class Solution {
public:int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int> f(n),g(n);for(int i = 1 ; i < n; i++){f[i] = f[i-1] + nums[i-1];}for(int i = n - 2; i >= 0; i--){g[i] = g[i+1] + nums[i+1];}for(int i = 0; i < n ; i++){if(g[i] == f[i]) return i;}return -1;}
};

---

4. 除自身以外數(shù)組的乘積

算法思路:

有了上一題思路二的方法, 對于這道題我們不難解決, 只需求出對于i之前的前綴積以及對于i之后的后綴積即可, 遍歷i位置此時answer[i]的位置就是f[i]*g[i], 但是注意細節(jié),對于f[0]和g[n-1]我們要處理成1, 默認第一個位置之前的積為1,最后一個位置也是.

編寫代碼:

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

---

5. 和為k的子數(shù)組

算法思路:

首先我們肯定會想到暴力求解, 但是時間復雜度為O(N^2), 那可不可以使用雙指針呢, 也就是我們的滑動窗口, 也不可以, 因為會有負數(shù), 并沒有單調(diào)性.

對于一個數(shù)組, 我們要求這個數(shù)組中和為k的子數(shù)組, 比如遍歷到i位置, 我們要求i往前的和為k的子數(shù)組, 僅需從0位置查找, 找到和為sum[i] - k的子數(shù)組即可, 所以我們的前綴和思想又可以派上用場了.

首先我們先計算出前綴和, 但是我們并不需要創(chuàng)建一個前綴和數(shù)組, 僅需把每一次的結(jié)果記錄到sum即可, 遍歷一遍數(shù)組, 遍歷到i位置就找i位置之前有沒有sum = nums[i] - k的, 我們可以把每一次的結(jié)果放到哈希表中, 但是注意我們并不需要i這個位置的和, 而是i之前的, 所以我們只保存i之前的前綴和即可, 如果有則ret++,繼續(xù)下一次查找, 但是注意如果整個數(shù)組等于k,也就是遍歷到第一個位置我們需要在0到-1這個區(qū)間查找, 所以我們需要處理hash[0] = 1.

編寫代碼:

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;int sum = 0, ret = 0;hash[0] = 1;for(int i = 0; i < nums.size();i++){sum += nums[i];if(hash.count(sum - k)) ret += hash[sum - k]; hash[sum]++;}return ret;}
};

6. 和可被K整除的子數(shù)組

算法思路:

本道題依然不能使用滑動窗口來解決, 更上一道題思路類似, 只不過我們這道題哈希表里面存放的是sum的余數(shù), 當遍歷到i位置的時候只需要判斷在i位置之前和除以k的余數(shù)是否等于sum除以k的余數(shù), 因為同余定理, 可以看下圖

也就是我們僅需在i位置前找到x%k等于sum%即可, 所以判斷的時候我們需要判斷sum的余數(shù), 所以哈希表里面我們需要存放余數(shù), 但是C++中余數(shù)是由負數(shù)的, 負數(shù)和正數(shù)取余結(jié)果不一樣, 所以我們需要進行修正. 使用sum遍歷數(shù)組, 并且求出sum的余數(shù)r, 然后先判斷sum之前的余數(shù)是否等于r, 如果等于則更新ret,最后將這個r也丟入到哈希表中.

編寫代碼:

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0 % k] = 1;int sum = 0, ret = 0;for(int i = 0; i < nums.size() ; i++){sum += nums[i];int r = (sum % k + k) % k;if(hash.count(r)) ret += hash[r];hash[r]++;}return ret;}
};

7. 連續(xù)數(shù)組

算法原理:

這一道題沒有單調(diào)性, 我們還是不能使用滑動窗口, 先把0修改成-1,我們就可以發(fā)現(xiàn)規(guī)律, i位置和在[0,i-1]位置的值相等, 即就能找到k數(shù)組, 因為正負抵消, 遍歷到i位置我們判斷該位置之前是否有和正好等于sum, 如果有則我們更新結(jié)果, 這里注意我們哈希表中需要存儲下標, 因為結(jié)果需要我們求出長度, 如果有重復的sum, 我們只保存最早出現(xiàn)的那個下標.

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;hash[0] = -1;int sum = 0 ,ret = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i] == 0 ? -1 : 1;if(hash.count(sum)) ret = max(ret,i - hash[sum]);else hash[sum] = i;}return ret;}
};

8. 矩陣區(qū)域和

算法思路:

首先讀懂題意, 如下圖所示, 也就是answer數(shù)組中的每一個位置就是mat當前位置的值向周圍拓展k個單位元素的和.接下來進行分析

這道題要求我們求出拓展k個單位的和, 我們應(yīng)該聯(lián)想到一個算法, 二維前綴和dp.回憶一下二維前綴和的用法.如果說我們要求一個矩陣的前綴和數(shù)組,
則dp[ i ] [ j ] = dp[ i - 1 ] [ j ] + dp[ i ] [ j-1 ] - dp[ i - 1] [j - 1] + arr[ i ] [ j ]

對于使用則有, 如果我們要求某一段區(qū)域的和,
則 ret = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

可以看出, 我們只要想求某段區(qū)域的和則前綴和數(shù)組中, 僅需知道這塊區(qū)域的左上角下標個右下角下標即可,本題我們也可以用這樣的思路, 但是有幾個細節(jié)需要注意:

1, 注意我們創(chuàng)建dp數(shù)組時, 為了避免越界訪問一般下標從1開始, 但是本題所給的數(shù)組mat是從下標0 開始, 所以我們它的dp數(shù)組需要稍作修改, 當時用到mat時, 將下標+1處理

然后創(chuàng)建我們的ret數(shù)組, ret數(shù)組中的每一個位置我們都需要使用到dp數(shù)組, 所以需要求每一個位置的左上角位置與右下角位置的下標, 以便于正確的使用dp數(shù)組.根據(jù)下面我們求出該區(qū)域與使用dp數(shù)組的映射關(guān)系, 然后對于每一個位置分別求其結(jié)果.

編寫代碼:

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++){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, y1 = max(0,j-k) + 1;int x2 = min(m-1,i+k) + 1, 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;}
};

---

完