目錄

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

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

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

4.可被k整除的子數(shù)組

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

---

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

. - 力扣（LeetCode）

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

????????即中心下標(biāo)左邊與右邊的元素和相等，如果沒有某一側(cè)沒有元素，那么值為0.

????????因?yàn)槭羌臃ㄟ\(yùn)算，那么左右元素相等的情況，加上中心元素，左右元素依然相等。

????????f[i]為前綴和，表示從0到i位置的數(shù)組元素和，遞推公式為? f[i] = f[i-1]+nums[i];

????????g[i]為后綴和，表示從 size-1 到i位置的數(shù)組元素和，遞推公式為·g[i] = g[i+1] + nums[i];

????????初始化時(shí)，f【0】，g【size-1】為0，不干擾運(yùn)算

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

. - 力扣（LeetCode）

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

??????????即某下標(biāo)左邊與右邊的元素的積，如果沒有某一側(cè)沒有元素，那么值為1.

????????f[i]為前綴積，表示從0到i-1位置的數(shù)組元素積，遞推公式為? f[i] = f[i-1]*nums[i-1];

????????g[i]為后綴積，表示從 size-1 到i+1位置的數(shù)組元素和，遞推公式為·g[i] = g[i+1] *?nums[i+1];

????????初始化時(shí)，f【0】，g【size-1】為1，不干擾運(yùn)算

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

. - 力扣（LeetCode）

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

????????因?yàn)閿?shù)組中的元素有正有負(fù)，并不具有單調(diào)性，因此不能使用滑動(dòng)窗口，那么我們使用前綴和。

????????以下標(biāo)為i的位置為終點(diǎn)，dp【i】為從nums【0】加到nums【i】的和

?????????1 6 -3 2 9 .....x

????????0 1? 2? 3? 4.... i

????????要想找到其中一段子數(shù)組和為k，可以等效為找從0向后找一個(gè)子數(shù)組，和為dp【i】-k。

????????因?yàn)槊看沃徽襥之前的位置，因此我們不需要真的創(chuàng)建一個(gè)前綴和，只需要記錄一個(gè)變量sum，來記錄此時(shí)的前綴和。

????????創(chuàng)建一個(gè)哈希表<int，int>分別存儲(chǔ)某個(gè)前綴和的值，和它的數(shù)目。

????????前綴和sum從0開始，加入哈希表，因此會(huì)缺失數(shù)組中無元素的情況，所以我們應(yīng)該初始化hash【0】 = 1.

????????我們每遍歷到一個(gè)前綴和sum的時(shí)候，只需要加上已經(jīng)在hash中存儲(chǔ)的，即i位置之前的前綴和中，是否有值為sum-k，加上即可，然后再加上本次增添的前綴和

4.可被k整除的子數(shù)組

. - 力扣（LeetCode）

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int>hash;int sum = 0;int ret = 0;hash[0] = 1;for(auto ch: nums){sum += ch; ret+= hash[((sum%k)+k)%k];hash[((sum%k)+k)%k]++;}return ret;}
};

思路同3完全相同

注意點(diǎn)：1.c++和java中負(fù)數(shù)取余操作為負(fù)數(shù),因此我們需要把取余操作的值+取余的值，再取余。

2.我們哈希表中存的是前綴和取余后的值。原因如下

0 1 2 3 4 ....i

假設(shè)從下標(biāo)4到i的數(shù)組和能被k整除，即，（前綴和i-前綴和3）% k == 0

根據(jù)同余定理，前綴和i % k == 前綴和3 % k。

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

. - 力扣（LeetCode）

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

????????直接做不好做，我們先把0轉(zhuǎn)化為-1，這樣子當(dāng)0與1數(shù)目相等時(shí)，其和為0。

????????這樣我們就把題目轉(zhuǎn)化為類似第三題的和為k的數(shù)組，此時(shí)和為0.

????????因此我們只需要尋找兩個(gè)前綴和相等的數(shù)組，將他們的下標(biāo)相減即可。

????????所以我們哈希表中儲(chǔ)存該下標(biāo)，hash[0]中儲(chǔ)存-1.

? ? ? ? 接著我們遍歷數(shù)組每次求出前綴和的時(shí)候，到哈希表中查看，如果已經(jīng)儲(chǔ)存下標(biāo)，那么我們相減。并與前面已經(jīng)求出的下標(biāo)差求最大，否則我們把下標(biāo)填入。下標(biāo)只需要更新最前面一個(gè)，因?yàn)橄蚝蟾聲r(shí)距離永遠(yuǎn)是更小的。

? ? ? ? 但是在判斷條件的時(shí)候我們遇到了問題，若更新出的數(shù)組下標(biāo)為0，那么我們將無法判斷，因此我們統(tǒng)一將數(shù)組下標(biāo)+2，這樣結(jié)果不變。