引言：

以下四道 Leetcode 題目屬于典型數組問題處理方法。它們采取類似的方法：利用哈希表保存數組前綴（前綴和、前綴01差值、前綴和對K的取余結果等等），然后判斷子數組合法性。時間復雜度可以達到 O(n) 級別。

問題描述：【Hash Table】523. Continuous Subarray Sum

解題思路：

這道題是給一個非負整數數組和整數 k，判斷數組是否含有連續(xù)子數組，其大小至少為 2，總和為 k 的倍數，即總和為 n*k，其中 n 也是一個整數。

做法如下：

• 遍歷整個數組，依次累加數組元素計算前綴和 presum，并將 presum 對 k 求余，求余結果只有 0~k-1 這 k 種情況（對 k 求余是為了滿足題目中總和為 k 的倍數的說法）。然后，將求余結果存入 Hash Table 中，其中，鍵為求余結果，值為當前位置索引。
• 如果遍歷到當前位置，presum 的求余結果已經在 Hash Table 中，表明從上一求余結果相同的位置到當前位置的子數組相加和是 k 的倍數，那么就判斷當前位置和上一位置的差值是否大于等于 2 （題目要求），如果是，返回 True；否則將求余結果存入 Hash Table 中。
• 在初始化的時候，Hash Table 中要加入 {0: -1}，它是邊界情況。

例1、以 nums = [2,4]，k = 3 舉例：

• presum = 2，presum % 3 = 2，則 dic = {0: -1, 2: 0}；
• presum += 4 = 6，presum % 3 = 0，這時發(fā)現(xiàn)求余結果 0 在 Hash Table 中出現(xiàn)過，說明位置 (-1, 1] 之間的數字之和是 3 的倍數。并且發(fā)現(xiàn)兩索引差值 i - dic[0] = 1 - (-1) = 2，大于等于 2，符合題意，返回 True。

例 1 也說明為什么要在初始化的時候在 Hash Table 中加入 {0: -1}。

例2、以 nums = [5,2,4]，k = 3 舉例：

• presum = 5，presum % 3 = 2，則 dic = {0: -1, 2: 0}；
• presum += 2 = 4，presum % 3 = 1，則 dic = {0: -1, 2: 0, 1: 1}；
• presum += 4 = 5，presum % 3 = 2，這時發(fā)現(xiàn)求余結果 2 在 Hash Table 中出現(xiàn)過，說明位置 (0, 2] 之間的數字之和是 3 的倍數。并且發(fā)現(xiàn)兩索引差值 i - dic[2] = 2 - 0 = 2，大于等于 2，符合題意，返回 True。

注意，這道題還有幾個邊界情況：（1）k 可能為負值和 0；（2）數組中可能出現(xiàn) [0,0] 這種情況。

例3、以 nums = [0, 0]，k = 0 舉例：

• presum = 0，因為 k 為 0， 所以不能進行取余操作，presum 結果還是 0 保持不變，這時發(fā)現(xiàn)結果 0 在 Hash Table 中出現(xiàn)過，說明位置 (-1, 0] 之間的數字之和是 0 的倍數。并且發(fā)現(xiàn)兩索引差值 i - dic[0] = 0 - (-1) = 1，1 小于 2，不符合題意，則跳過，判斷下一個位置。
• presum += nums[1] = 0，這時發(fā)現(xiàn)結果 0 在 Hash Table 中出現(xiàn)過，說明位置 (-1, 1] 之間的數字之和是 0 的倍數。并且發(fā)現(xiàn)兩索引差值 i - dic[0] = 1 - (-1) = 2，1 大于等于 2，符合題意，返回 True。

考慮到上述 3 個例子的情況，我們就可以寫出代碼了。

Python3 實現(xiàn)：

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        dic = {0: -1}  # 保存前綴和的位置索引，{0:-1}為了處理邊界情況
        presum = 0
        for i in range(len(nums)):
            presum += nums[i]
            if k != 0:  # k非0才對前綴和進行求余操作
                presum %= k
            if presum in dic:  # 前綴和在dic中找到，說明當前位置與dic[presum]之間數字之和為k
                if i - dic[presum] >= 2:  # 還要滿足長度大于等于2
                    return True
            else:
                dic[presum] = i
        return False

問題描述：【Hash Table】525. Contiguous Array

解題思路：

這道題是給一個 01 數組，求含有相同數量的 0 和 1 的最長連續(xù)子數組的長度。

方法1（前綴 01 差值）：

• 遍歷數組的每個位置，統(tǒng)計數字 0 和 1 的個數，并計算前綴 01 差值；
• 如果該差值在后續(xù)還會出現(xiàn)，說明從上一位置到當前位置 01 個數相等，更新最大值；
• 如果該差值沒有出現(xiàn)過，就保存在 Hash Table 中，鍵為差值，值為當前位置索引;
• 初始化時，將 {0: -1} 存入 Hash Table，便于邊界情況判斷。

例如，nums = [1,1,0,0,0,1]，cnt = [0, 0] 統(tǒng)計前綴 01 個數，對于每個位置 i：

• sub = cnt[0] - cnt[1] = -1，-1 不在 dic 中，則保存該差值 dic = {0: -1, -1: 0}；
• sub = cnt[0] - cnt[1] = -2，-2 不在 dic 中，則保存該差值 dic = {0: -1, -1: 0, -2: 1}；
• sub = cnt[0] - cnt[1] = -1，-1 在 dic 中，說明上一次出現(xiàn) -1 差值的位置到當前位置，即區(qū)間 (0, 2] 之間的 01 個數相等，則更新最大長度 max_ = i - dic[-1] = 2 - 0 = 2；
• sub = cnt[0] - cnt[1] = 0，0 在 dic 中，說明上一次出現(xiàn) 0 差值的位置到當前位置，即區(qū)間 (-1, 3] 之間的 01 個數相等，則更新最大長度 max_ = i - dic[0] = 3 - (-1) = 4，這也是為什么要初始化 dic = {0: -1} 的原因；
• sub = cnt[0] - cnt[1] = 1，1 不在 dic 中，則保存該差值 dic = {0: -1, -1: 0, -2: 1, 1: 4}；
• sub = cnt[0] - cnt[1] = 2，2 不在 dic 中，則保存該差值 dic = {0: -1, -1: 0, -2: 1, 1: 4, 2: 5}；
• sub = cnt[0] - cnt[1] = 1，1 在 dic 中，則區(qū)間 (4, 6] 之間 01 個數相等，長度為 2，但是小于最大長度 max_，跳過。
• 最后得到最大長度 max_ = 4。

Python3 實現(xiàn)：

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        dic = {0: -1}  # 保存01差值的位置索引，{0:-1}為了處理邊界情況
        cnt = [0, 0]  # 統(tǒng)計01次數
        max_ = 0
        for k, num in enumerate(nums):
            cnt[num] += 1  # 01計數
            sub = cnt[0] - cnt[1]  # 計算0與1的差值，可能為負值
            if sub not in dic:
                dic[sub] = k
            else:
                max_ = max(max_, k - dic[sub])
        return max_

方法2（前綴和為0）：

如果我們把數組中的所有 0 全部變成 -1，那么這道題就變成了求和為 0 的最長連續(xù)子數組長度。那么類似于上面的 Leetcode 523，我們計算前綴和，判斷前綴和是否在 Hash Table 中再次出現(xiàn)，如果再次出現(xiàn)，說明兩位置之間的和為 0，即兩位置之間01個數相同，則更新最大長度；否則，將前綴和保存在 Hash Table 中。

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        dic = {0: -1}  # 保存前綴和的位置索引，{0:-1}為了處理邊界情況
        presum, max_ = 0, 0
        for k, num in enumerate(nums):
            if num == 0:  # 把0改成-1計算前綴和
                presum += (-1)
            else:
                presum += 1
            if presum not in dic:
                dic[presum] = k
            else:  # 前綴和再次出現(xiàn)，說明兩位置之間和為0，即01個數相等
                max_ = max(max_, k - dic[presum])
        return max_

問題描述：【Hash Table】560. Subarray Sum Equals K

解題思路：

這道題是給一個數組，求連續(xù)子數組和為 k 的總數。

這道題和 Leetcode 523 以及 Leetcode 525 的方法 2 類似，也是先求前綴和 presum，但是區(qū)別在于，前面兩道題判斷 presum 是否再次出現(xiàn)在 Hash Table 中，但是這道題要判斷 presum - k 是否再次出現(xiàn)在 Hash Table 中。并且，還有一點不同的是，因為要計算子數組的總數，所以 Hash Table 中的鍵還是前綴和 presum，但是值要存儲當前前綴和出現(xiàn)的次數，而不像前兩道題中存儲當前位置索引。初始化時，Hash Table 中 {0: 1}，用于邊界情況處理。

舉個例子：nums = [2, 4, 1, 0, 5, -7]，k = 5

• presum = 2，2 - k 不在 dic 中，則把 presum 保存在 dic = {0: 1, 2: 1}；
• presum += 6，6 - k 不在 dic 中，則把 presum 保存在 dic = {0: 1, 2: 1, 6: 1}；
• presum += 7，7 - k 在 dic 中，說明上一次出現(xiàn)前綴和 2 的位置到當前位置之間的數字之和為 k，則 ans += dic[7-k] = 1，并把 presum 保存在 dic = {0: 1, 2: 1, 6: 1, 7: 1}；
• presum += 7，7 - k 在 dic 中，說明上一次出現(xiàn)前綴和 2 的位置到當前位置之間的數字之和為 k，則 ans += dic[7-k] = 2，并把 presum 保存在 dic = {0: 1, 2: 1, 6: 1, 7: 2}（前綴和 7 之前出現(xiàn)過一次，直接累加）；
• presum += 12，12 - k 在 dic 中，說明上一次出現(xiàn)前綴和 7 的位置到當前位置之間的數字之和為 k，則 ans += dic[12-k] = 4，并把 presum 保存在 dic = {0: 1, 2: 1, 6: 1, 7: 2, 12: 1}；
• presum += 5，5 - k 在 dic 中，說明上一次出現(xiàn)前綴和 0 的位置到當前位置之間的數字之和為 k，則 ans += dic[5-k] = 5，并把 presum 保存在 {0: 1, 2: 1, 6: 1, 7: 2, 12: 1, 5: 1}，這也是為什么初始化 Hash Table 為 {0: -1} 的原因；**
• 數組遍歷完畢，ans = 5 就是答案。

Python3 實現(xiàn)：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dic = {0: 1}  # 保存前綴和出現(xiàn)次數，{0:-1}為邊界情況
        presum, ans = 0, 0
        for num in nums:
            presum += num
            if (presum - k) in dic:  # 前綴和減去目標值在dic中找到，累加結果
                ans += dic[presum-k]
            if presum not in dic:  # 將前綴和出現(xiàn)次數保存到dic中
                dic[presum] = 1
            else:
                dic[presum] += 1
        return ans

問題描述：【Hash Table】974. Subarray Sums Divisible by K

解題思路：

這道題是給一個數組，求連續(xù)子數組之和可以被 K 整除的總數。

經過了上面三道題的歷練，這道題自然很容易求解。題目中“連續(xù)子數組之和可以被 K 整除”類似于 Leetcode 523 的做法，要先將前綴和 presum 對 K 取余，并且判斷 presum 是否在 Hash Table 中出現(xiàn)過；而它是一個計算總數的問題，類似于 Leetcode 560，Hash Table 中保存的應該是前綴和出現(xiàn)的次數。因此，很快可以寫出代碼。

Python3 實現(xiàn)：

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        dic = collections.defaultdict(int)
        dic[0] = 1
        ans, presum = 0, 0
        for a in A:
            presum += a
            presum %= K  # 先將前綴和對K取余
            if presum in dic:
                ans += dic[presum]
            dic[presum] += 1  # 統(tǒng)計前綴和出現(xiàn)次數
        return ans

總結：

計算數組前綴（前綴和、前綴01差值、前綴和對K的取余結果等等）保存在 Hash Table 中，等到下次再次出現(xiàn)相同的前綴時，說明兩次位置之間的數字是滿足題意的。利用這個特點，我們能做到在 O(n) 的時間內求解。