一、引入
關(guān)于前綴和和哈希這兩個概念大家都不陌生，在之前的文章中也有過介紹：前綴和與差分算法詳解
而哈希表最經(jīng)典的一題莫過于兩數(shù)之和
題目鏈接
題目描述：
給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標(biāo)值 target，請你在該數(shù)組中找出 和為目標(biāo)值 target 的那 兩個 整數(shù)，并返回它們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。
你可以按任意順序返回答案。
示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因?yàn)?nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]
只會存在一個有效答案
思路分析：
我們在遍歷這個數(shù)組要做兩件事：
假設(shè)現(xiàn)在遍歷到下標(biāo)為idx的位置。
1?? 查看target - nums[idx]是否在哈希表中，如果在，說明這兩個數(shù)加起來就是目標(biāo)和，那么就找到了兩個下標(biāo)，一個是hash[target - nums[idx]]，一個是當(dāng)前位置idx。
2?? 用哈希表記錄兩個數(shù)據(jù)，first記錄當(dāng)前位置的值，second記錄當(dāng)前位置的下標(biāo)。
代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-427634.html
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
int n = nums.size();
for(int i = 0; i < n; i++)
{
if(hash.find(target - nums[i]) != hash.end())
{
return {hash[target - nums[i]], i};
}
hash[nums[i]] = i;
}
return {};
}
};
二、前綴和與哈希表的結(jié)合
用一個例子來說明以下：
假設(shè)我們要尋和為5的連續(xù)子數(shù)組的個數(shù)，那么只要前綴和中任意兩個數(shù)的差值為5，那么就找到了子數(shù)組。
那么我們就可以直接用哈希表把前綴和的數(shù)據(jù)存儲起來，first存前綴和的值，second用來標(biāo)識有多少個子數(shù)組。
這里首先要注意初始化哈希表把0的位置先設(shè)置成1：hash[0] = 1，因?yàn)楫?dāng)我們計(jì)算前綴和為5的位置的時候，就標(biāo)識了從0 ~ 5存在和為5的連續(xù)子數(shù)組。
假設(shè)目標(biāo)和為k，遍歷到i位置。
所以現(xiàn)在我們在計(jì)算前綴和的同時看看是否存在hash[k - nums[i]]，這個的數(shù)值大小就代表有多少個連續(xù)的子數(shù)組和。那么為什么會存在多個呢？
因?yàn)榭赡軘?shù)組存在負(fù)數(shù)，這樣就會導(dǎo)致出現(xiàn)這種情況：
那么省略號這段區(qū)間的前綴總和就為0，所以就會存在兩段子數(shù)組和為5的區(qū)間。
三、例題
3.1 和為 K 的子數(shù)組
題目鏈接
題目描述：
給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k ，請你統(tǒng)計(jì)并返回 該數(shù)組中和為 k 的連續(xù)子數(shù)組的個數(shù) 。
示例 1：
輸入：nums = [1,1,1], k = 2
輸出：2
示例 2：
輸入：nums = [1,2,3], k = 3
輸出：2
思路分析：
這個題如果我們只使用前綴和：先計(jì)算前綴和，然后依次遍歷看是否有兩個數(shù)字的差值為k。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
// 前綴和數(shù)組
vector<int> sums(n + 1);
for(int i = 0; i < n; i++)
{
sums[i + 1] = sums[i] + nums[i];
}
int res = 0;
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
if(sums[j + 1] - sums[i] == k)
{
res++;
}
}
}
return res;
}
};
但是提交會發(fā)現(xiàn)運(yùn)行超時。
而由于這道題只關(guān)心次數(shù)，不關(guān)注具體的解，所以我們能用哈希表來優(yōu)化效率。
具體的做法在上面已經(jīng)詳細(xì)介紹過。
代碼：
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int, int> hash;
int res = 0;
hash[0] = 1;
int sum = 0;
for(int i = 0; i < n; i++)
{
sum += nums[i];
res += hash[sum - k];
hash[sum]++;
}
return res;
}
};
3.2 統(tǒng)計(jì)「優(yōu)美子數(shù)組」
題目鏈接
題目描述：
給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k。如果某個連續(xù)子數(shù)組中恰好有 k 個奇數(shù)數(shù)字，我們就認(rèn)為這個子數(shù)組是「優(yōu)美子數(shù)組」。
請返回這個數(shù)組中 「優(yōu)美子數(shù)組」 的數(shù)目。
示例 1：
輸入：nums = [1,1,2,1,1], k = 3
輸出：2
解釋：包含 3 個奇數(shù)的子數(shù)組是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：
輸入：nums = [2,4,6], k = 1
輸出：0
解釋：數(shù)列中不包含任何奇數(shù)，所以不存在優(yōu)美子數(shù)組。
示例 3：
輸入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
輸出：16
思路分析：
這道題乍一看無從下手，但其實(shí)這道題跟上面一道題沒什么區(qū)別，只要把偶數(shù)看成0，奇數(shù)看成1，就直接轉(zhuǎn)化成了和為K的子數(shù)組問題了。
代碼：
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size();
int res = 0;
unordered_map<int, int> hash;
hash[0] = 1;
int sum = 0;
for(int i = 0; i < n; i++)
{
// 偶數(shù)為0,奇數(shù)為1
int ret = 0;
if(nums[i] % 2)
{
ret = 1;
}
sum += ret;
res += hash[sum - k];
hash[sum]++;
}
return res;
}
};
3.3 路徑總和III
題目鏈接
題目描述：
給定一個二叉樹的根節(jié)點(diǎn) root ，和一個整數(shù) targetSum ，求該二叉樹里節(jié)點(diǎn)值之和等于 targetSum 的 路徑 的數(shù)目。
路徑 不需要從根節(jié)點(diǎn)開始，也不需要在葉子節(jié)點(diǎn)結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）。
示例 1：
輸入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
輸出：3
解釋：和等于 8 的路徑有 3 條，如圖所示。
示例 2：
輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出：3
方法一：
這道題可以直接用暴力遍歷，每個節(jié)點(diǎn)都往下統(tǒng)計(jì)到葉子節(jié)點(diǎn)，看有多少個。
代碼：
class Solution {
public:
int dfs(TreeNode* root, long long targetSum)
{
if(root == nullptr)
{
return 0;
}
int ret = 0;
if(targetSum - root->val == 0)
{
ret++;
}
ret += dfs(root->left, targetSum - root->val);
ret += dfs(root->right, targetSum - root->val);
return ret;
}
int pathSum(TreeNode* root, int targetSum) {
if(root == nullptr)
{
return 0;
}
int res = dfs(root, targetSum);
res += pathSum(root->left, targetSum);
res += pathSum(root->right, targetSum);
return res;
}
};
方法二：
第二個方法當(dāng)然是使用前綴和+哈希表算法。
我們邊遞歸邊求前綴和，統(tǒng)計(jì)的方法還是跟上面一樣，這里要注意的是當(dāng)回溯的時候記住要把當(dāng)前的位置給去掉（沒遞歸到當(dāng)前位置的狀態(tài)）。
代碼：
class Solution {
public:
unordered_map<long long, int> hash;
int cnt;
void dfs(TreeNode* root, long long sum, int target)
{
if(root == nullptr)
{
return;
}
sum += root->val;
cnt += hash[sum - target];
hash[sum]++;
dfs(root->left, sum, target);
dfs(root->right, sum, target);
hash[sum]--;
}
int pathSum(TreeNode* root, int targetSum) {
hash[0] = 1;
cnt = 0;
dfs(root, 0, targetSum);
return cnt;
}
};
四、總結(jié)
我們通過上面的問題可以總結(jié)出規(guī)律，遇到求連續(xù)的和的時候我們就應(yīng)該想到用前綴和算法，而如果題目只關(guān)心次數(shù)，不關(guān)注具體的解，我們就可以使用（前綴和+哈希表）算法。文章來源地址http://www.zghlxwxcb.cn/news/detail-427634.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】前綴和+哈希表算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
