I238. 除自身以外數(shù)組的乘積 - 力扣（LeetCode）

給你一個整數(shù)數(shù)組?nums，返回?數(shù)組?answer?，其中?answer[i]?等于?nums?中除?nums[i]?之外其余各元素的乘積?。

題目數(shù)據(jù)?保證?數(shù)組?nums之中任意元素的全部前綴元素和后綴的乘積都在??32 位?整數(shù)范圍內(nèi)。

請?不要使用除法，且在?O(n)?時間復(fù)雜度內(nèi)完成此題。

示例 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 <= 105
-30 <= nums[i] <= 30
保證 數(shù)組 nums之中任意元素的全部前綴元素和后綴的乘積都在  32 位 整數(shù)范圍內(nèi)進階：你可以在 O(1) 的額外空間復(fù)雜度內(nèi)完成這個題目嗎？（ 出于對空間復(fù)雜度分析的目的，輸出數(shù)組 不被視為 額外空間。）

題目已經(jīng)給的很明顯了，就是使用前綴積 和 后綴積 的方式來求解，這種方式其實 是一個簡化的 動態(tài)規(guī)劃。

用兩個數(shù)組，分別存儲 從起始位置到 i 位置的乘積 和 從 末尾位置 到 i 位置的乘積；

上述兩個結(jié)果對應(yīng)的就是 f[i]? 和? g[i] 。

遞推公式：

f[i] = f[i - 1] * nums[i - 1];g[i] = g[i + 1] * nums[i + 1];

f[0] 和 g[nums.size()] 都是需要自己手動算的，上述遞推公式是算不出來的。

如果我們像計算題目描述的某個位置（比如是 i 位置）的 前綴積 和 后綴積的話，只需要計算? ? ? ? f[i] * g[i] 既可，因為?f[i] 表示的就是 i 之前的 所有積，g[i] 表示的就是 i 之后的所有的積。

完整代碼：

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

---

I560. 和為 K 的子數(shù)組 - 力扣（LeetCode）

給你一個整數(shù)數(shù)組?nums?和一個整數(shù)?k?，請你統(tǒng)計并返回?該數(shù)組中和為?k?的子數(shù)組的個數(shù)?。

子數(shù)組是數(shù)組中元素的連續(xù)非空序列。

示例 1：輸入：nums = [1,1,1], k = 2
輸出：2
示例 2：輸入：nums = [1,2,3], k = 3
輸出：2

?還是使用前綴和，我們可以使用 找到一個前綴和 sum[i] 就表示，從數(shù)組 0 號位置開始，到 i 位置的所有元素之和。

那么，我們只需要在這個區(qū)間當(dāng)中找到 在 [0,i] 這個區(qū)間當(dāng)中,某一個位置作為起始位置（假設(shè)為 j? ?），到 i 位置，這個子數(shù)組的 元素之和等于k，那么 ，[0,j] 這個區(qū)間當(dāng)中各個 元素之和就是? ? ? ? ? ?sum[i] - k;

?往后，只需要? i 往后尋找，就不會找漏。

但是，上述還是有一個問題，如果我們直接遍歷 sum 數(shù)組的，來找到 j 這個位置的話，在加上 創(chuàng)建 sum 數(shù)組的時間復(fù)雜度，實際上，這個算法的整個 時間復(fù)雜度其實還不如 暴力解法。

所以，其實我們不用? 循環(huán)一個一個 去找? j? 位置，我們可以利用一個 hash 表來 代替 sum 存儲的這些 前綴和的值，也就是代替 sum 存儲 其中的每一個元素。

哈希表：? hash<前綴和值， 前綴和出現(xiàn)次數(shù)>

這樣，如果我們 想 在? [0,i] 這個區(qū)間當(dāng)中, 找到 j 這個位置，只需要 利用 hash 表的快速查找來查找 在當(dāng)前hash 表當(dāng)中有沒有 sum[i] - k 這個前綴和，同時，利用 hash 表當(dāng)中的 count（）函數(shù)，可以快速查找，這個?sum[i] - k ?出現(xiàn)次數(shù)。

關(guān)于前綴和加入hash 表的時機：
因為我們的前綴和算法，是要找的是?在 [0,i] 這個區(qū)間當(dāng)中 ，有多少個 前綴和 等于sum[i] - k;? ?。

如果直接 在一開始就把 sum 計算出來，然后把 區(qū)間當(dāng)中 前綴和 和 前綴和出現(xiàn)的次數(shù)加入到 hash 表當(dāng)中是會計算到 i 后面的值。所以不行。

所以，我們在計算 i 位置之前，哈希表里面值存儲 [0, i - 1] 位置的前綴和。

還有一種情況，當(dāng) 當(dāng)前的整個的 前綴和 等于 k 的話，那么，在上述的算法當(dāng)中，其實我們是找不到這個情況的，因為 我們找到的是 等于 k 的子區(qū)間，這個子區(qū)間的起始位置上述說過了，是 j ，那么 滿足? ?sum[i] - k;?的 區(qū)間就是 [0, j - 1]， 那么在這個情況當(dāng)中就是 [0, -1] 這個區(qū)間，這個區(qū)間是不存在的。

所以，我們開始就要默認 數(shù)組當(dāng)中有一個 和為 0 的前綴和，即： hash[0] = 1;

完整代碼：

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> hash(nums.size());hash[0] = 1;int sum = 0, ret = 0; // sum 代替sum數(shù)組，利用變量給 hash 當(dāng)中賦值；ret 返回個數(shù)for(auto& e : nums){sum += e; // 計算當(dāng)前的前綴和// 計算滿足 條件的區(qū)間，是否在 hash 當(dāng)中出現(xiàn)。count（）函數(shù)判斷是否出現(xiàn)//  出現(xiàn)計數(shù)器 加上 這個前綴和 在 hash 當(dāng)中出現(xiàn)的次數(shù)if(hash.count(sum - k)) ret += hash[sum - k]; hash[sum]++;                  }return ret;}
};

---

I974. 和可被 K 整除的子數(shù)組 - 力扣（LeetCode）

給定一個整數(shù)數(shù)組?nums?和一個整數(shù)?k?，返回其中元素之和可被?k?整除的（連續(xù)、非空）?子數(shù)組?的數(shù)目。

子數(shù)組?是數(shù)組的?連續(xù)?部分。

示例 1：輸入：nums = [4,5,0,-2,-3,1], k = 5
輸出：7
解釋：
有 7 個子數(shù)組滿足其元素之和可被 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

要解決這道題目，首先要知道 同于定理?

也就是 如果 a 和 b 的差值，除上 p ，如果是整除的話，也就是余數(shù)是零的話，a 除上 p 的余數(shù) =? ? b 除上 p 的余數(shù)。

而且，還需要清楚，在C++ 當(dāng)中， [負數(shù) % 正數(shù)] 的結(jié)果是 一個負數(shù)。

?也就是說，其實[負數(shù) % 正數(shù)] ? 其實結(jié)果也是一個 余數(shù)，但是這個余數(shù)是負數(shù)。

所以，針對這種情況，我們要對這個負數(shù)進行修正，把他修正為 正數(shù)。

所以，當(dāng)我們在計算?[負數(shù) % 正數(shù)] 的 結(jié)果之時，其實，計算出的負數(shù)的結(jié)果在加上 模數(shù)（也就是其中的正數(shù)），其實就是對應(yīng)的正數(shù)的結(jié)果。如下圖所示：
?

上述的計算方式對于 a 是負數(shù)的情況來說，計算出的結(jié)果就是修正之后的結(jié)果，也就是修正為 正數(shù)之后的結(jié)果。

但是上述的 修正方式對于 a 是正數(shù)的情況是 計算錯誤的，因為 對于 a 是正數(shù)的情況來說， a % b 本來就是 正確的結(jié)果，但是后面又加上了 一個 b，所以是不正確的。

所以，為了 正數(shù)和負數(shù)統(tǒng)一，我們共用的方式就是? 在上述計算式子當(dāng)中，再 % b 即可。

上述式子就是我們想要的i修正公式了。

---

所以，按照和這個問題其實就和上述 和為K的子數(shù)組求解方式一樣了。

先求出所有的 從 0 號數(shù)組位置開始的 所以前綴模，保存到一個數(shù)組當(dāng)中，然后 求出 與 K 模的余數(shù)即可。

同樣優(yōu)化方式和上述一樣，不需要多定義一個 數(shù)組來保存 前綴模，這樣也不好 查找對應(yīng)的前綴模，只需要 用一個 hash表來存儲即可。

上述問題就被簡化為了 在 [0, i - 1] 這個區(qū)間當(dāng)中，找到有多少個前綴和 的 余數(shù)等于 (sum %? k + k ) % k。

完整代碼：
?

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int, int> hash;hash[0 % k] = 1; // 0 這數(shù)的余數(shù)int sum = 0, ret = 0;for(auto& e : nums){sum += e;int r = (sum%k + k) % k;if(hash.count(r)) ret += hash[r];hash[r]++;}return ret;}
};

---

I525. 連續(xù)數(shù)組 - 力扣（LeetCode）

?給定一個二進制數(shù)組?nums?, 找到含有相同數(shù)量的?0?和?1?的最長連續(xù)子數(shù)組，并返回該子數(shù)組的長度。

示例 1:輸入: nums = [0,1]
輸出: 2
說明: [0, 1] 是具有相同數(shù)量 0 和 1 的最長連續(xù)子數(shù)組。
示例 2:輸入: nums = [0,1,0]
輸出: 2
說明: [0, 1] (或 [1, 0]) 是具有相同數(shù)量0和1的最長連續(xù)子數(shù)組。

在數(shù)組當(dāng)中，所有的 元素的值要么是 0 ，要么是1。我們需要找到一個 符合要求的最長的連續(xù)的子數(shù)組，返回這個子數(shù)組的長度。

我們在統(tǒng)計個數(shù)的時候，其實是可以做到轉(zhuǎn)化的，如果把 0 全部替換為-1，那么我們統(tǒng)計個數(shù)的問題，其實就 轉(zhuǎn)化成了 找到一個 元素之和等于 0 的子數(shù)組。

所以，這道題目就可以使用前綴和的方法來解決。

使用hash 表來存儲 前綴和為 sum 的區(qū)間，所以嗎，應(yīng)該是 unordered_map<sum, i > （其中 sum 是前綴和，i 是這個前綴和區(qū)間的下標）。

當(dāng)找到某一個下標，和為? sum，計算出 這個區(qū)間的長度，就把這個 對應(yīng)的 綁定的值存入到哈希表當(dāng)中。

如果有重復(fù)的 sum，但是區(qū)間不一樣，不需要重新更新原本在 hash 表當(dāng)中的 <sum , i>， 只需要保留之前存入的 <sum, i> 即可。因為 ，我們需要找到 子區(qū)間最長的子數(shù)組，那么 下標應(yīng)該是越考左 ，那么 計算出的 子區(qū)間 長度才是最大的。

同樣，為了處理特殊情況：當(dāng) [0?, i] 這個子區(qū)間計算出的前綴和就是0了，那么按照上述? 和為K的子數(shù)組 這個題目當(dāng)中邏輯去 找到子區(qū)間的話，就會在 -1 為開始的區(qū)間去找。

所以，我們需要 在開始 默認 一個子區(qū)間的前綴和是0，即? hash[0] = -1;

上述的過程就可以找出所有的 合法的子數(shù)組了，現(xiàn)在就是如何計算這個子數(shù)組的區(qū)間大小？

如上，我們只需要找出 i 和 j 兩個下標，使得 [0, i] 的 前綴和 和 [0, j] 的前綴和 相等即可。

?所以我們計算出的 區(qū)間的 長度就是 i - j 。

完整代碼：

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int ,int> hash;hash[0] = -1;   // 默認 剛開始 哈希表當(dāng)中有一個 前綴和為0 的區(qū)間int sum = 0, ret = 0;for(int i = 0 ;i < nums.size(); i++){sum += nums[i] == 0 ? -1 : 1; // 如果是 0 就加-1，如是1 就加 1// 如果 sum 在hash 當(dāng)中存在，說明此時就已經(jīng)找到了 符合條件的子區(qū)間// 那么就更新的 ret 返回值。if(hash.count(sum)) ret = max(ret, i - hash[sum] + 1 - 1);else hash[sum] = i;  // sum 在 hash 當(dāng)中不存在，那么 就添加一個 hash 元素}return ret;}
};