引言：

以下四道 Leetcode 題目屬于典型數(shù)組問(wèn)題處理方法。它們采取類似的方法：利用哈希表保存數(shù)組前綴（前綴和卤妒、前綴01差值甥绿、前綴和對(duì)K的取余結(jié)果等等），然后判斷子數(shù)組合法性则披。時(shí)間復(fù)雜度可以達(dá)到 O(n) 級(jí)別共缕。

問(wèn)題描述：【Hash Table】523. Continuous Subarray Sum

解題思路：

這道題是給一個(gè)非負(fù)整數(shù)數(shù)組和整數(shù) k，判斷數(shù)組是否含有連續(xù)子數(shù)組士复，其大小至少為 2图谷，總和為 k 的倍數(shù)，即總和為 n*k阱洪，其中 n 也是一個(gè)整數(shù)便贵。

做法如下：

• 遍歷整個(gè)數(shù)組，依次累加數(shù)組元素計(jì)算前綴和 presum冗荸，并將 presum 對(duì) k 求余承璃，求余結(jié)果只有 0~k-1 這 k 種情況（對(duì) k 求余是為了滿足題目中總和為 k 的倍數(shù)的說(shuō)法）。然后俏竞，將求余結(jié)果存入 Hash Table 中绸硕，其中堂竟，鍵為求余結(jié)果，值為當(dāng)前位置索引玻佩。
• 如果遍歷到當(dāng)前位置出嘹，presum 的求余結(jié)果已經(jīng)在 Hash Table 中，表明從上一求余結(jié)果相同的位置到當(dāng)前位置的子數(shù)組相加和是 k 的倍數(shù)咬崔，那么就判斷當(dāng)前位置和上一位置的差值是否大于等于 2 （題目要求）税稼，如果是，返回 True垮斯；否則將求余結(jié)果存入 Hash Table 中郎仆。
• 在初始化的時(shí)候，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，這時(shí)發(fā)現(xiàn)求余結(jié)果 0 在 Hash Table 中出現(xiàn)過(guò)川陆，說(shuō)明位置 (-1, 1] 之間的數(shù)字之和是 3 的倍數(shù)剂习。并且發(fā)現(xiàn)兩索引差值 i - dic[0] = 1 - (-1) = 2，大于等于 2较沪，符合題意鳞绕，返回 True。

例 1 也說(shuō)明為什么要在初始化的時(shí)候在 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，這時(shí)發(fā)現(xiàn)求余結(jié)果 2 在 Hash Table 中出現(xiàn)過(guò)镣衡，說(shuō)明位置 (0, 2] 之間的數(shù)字之和是 3 的倍數(shù)霜定。并且發(fā)現(xiàn)兩索引差值 i - dic[2] = 2 - 0 = 2档悠，大于等于 2，符合題意望浩，返回 True辖所。

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

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

• presum = 0酥宴，因?yàn)?k 為 0， 所以不能進(jìn)行取余操作您觉，presum 結(jié)果還是 0 保持不變拙寡，這時(shí)發(fā)現(xiàn)結(jié)果 0 在 Hash Table 中出現(xiàn)過(guò)，說(shuō)明位置 (-1, 0] 之間的數(shù)字之和是 0 的倍數(shù)琳水。并且發(fā)現(xiàn)兩索引差值 i - dic[0] = 0 - (-1) = 1倒庵，1 小于 2，不符合題意炫刷，則跳過(guò)擎宝，判斷下一個(gè)位置。
• presum += nums[1] = 0浑玛，這時(shí)發(fā)現(xiàn)結(jié)果 0 在 Hash Table 中出現(xiàn)過(guò)绍申，說(shuō)明位置 (-1, 1] 之間的數(shù)字之和是 0 的倍數(shù)。并且發(fā)現(xiàn)兩索引差值 i - dic[0] = 1 - (-1) = 2顾彰，1 大于等于 2极阅，符合題意，返回 True涨享。

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

Python3 實(shí)現(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才對(duì)前綴和進(jìn)行求余操作
                presum %= k
            if presum in dic:  # 前綴和在dic中找到奔脐，說(shuō)明當(dāng)前位置與dic[presum]之間數(shù)字之和為k
                if i - dic[presum] >= 2:  # 還要滿足長(zhǎng)度大于等于2
                    return True
            else:
                dic[presum] = i
        return False

問(wèn)題描述：【Hash Table】525. Contiguous Array

解題思路：

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

方法1（前綴 01 差值）：

• 遍歷數(shù)組的每個(gè)位置髓迎，統(tǒng)計(jì)數(shù)字 0 和 1 的個(gè)數(shù)，并計(jì)算前綴 01 差值建丧；
• 如果該差值在后續(xù)還會(huì)出現(xiàn)排龄，說(shuō)明從上一位置到當(dāng)前位置 01 個(gè)數(shù)相等，更新最大值翎朱；
• 如果該差值沒(méi)有出現(xiàn)過(guò)橄维，就保存在 Hash Table 中尺铣，鍵為差值，值為當(dāng)前位置索引;
• 初始化時(shí)争舞，將 {0: -1} 存入 Hash Table迄埃，便于邊界情況判斷。

例如兑障，nums = [1,1,0,0,0,1]侄非，cnt = [0, 0] 統(tǒng)計(jì)前綴 01 個(gè)數(shù)，對(duì)于每個(gè)位置 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 中除秀，說(shuō)明上一次出現(xiàn) -1 差值的位置到當(dāng)前位置，即區(qū)間 (0, 2] 之間的 01 個(gè)數(shù)相等算利，則更新最大長(zhǎng)度 max_ = i - dic[-1] = 2 - 0 = 2册踩；
• sub = cnt[0] - cnt[1] = 0，0 在 dic 中效拭，說(shuō)明上一次出現(xiàn) 0 差值的位置到當(dāng)前位置暂吉，即區(qū)間 (-1, 3] 之間的 01 個(gè)數(shù)相等，則更新最大長(zhǎng)度 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 個(gè)數(shù)相等熔号，長(zhǎng)度為 2，但是小于最大長(zhǎng)度 max_鸟整，跳過(guò)。
• 最后得到最大長(zhǎng)度 max_ = 4朦蕴。

Python3 實(shí)現(xiàn)：

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

方法2（前綴和為0）：

如果我們把數(shù)組中的所有 0 全部變成 -1，那么這道題就變成了求和為 0 的最長(zhǎng)連續(xù)子數(shù)組長(zhǎng)度涉茧。那么類似于上面的 Leetcode 523赴恨，我們計(jì)算前綴和，判斷前綴和是否在 Hash Table 中再次出現(xiàn)伴栓，如果再次出現(xiàn)伦连，說(shuō)明兩位置之間的和為 0，即兩位置之間01個(gè)數(shù)相同钳垮，則更新最大長(zhǎng)度惑淳；否則，將前綴和保存在 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計(jì)算前綴和
                presum += (-1)
            else:
                presum += 1
            if presum not in dic:
                dic[presum] = k
            else:  # 前綴和再次出現(xiàn)，說(shuō)明兩位置之間和為0肚医，即01個(gè)數(shù)相等
                max_ = max(max_, k - dic[presum])
        return max_

問(wèn)題描述：【Hash Table】560. Subarray Sum Equals K

解題思路：

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

這道題和 Leetcode 523 以及 Leetcode 525 的方法 2 類似肠套，也是先求前綴和 presum舰涌，但是區(qū)別在于，前面兩道題判斷 presum 是否再次出現(xiàn)在 Hash Table 中你稚，但是這道題要判斷 presum - k 是否再次出現(xiàn)在 Hash Table 中舵稠。并且，還有一點(diǎn)不同的是入宦，因?yàn)橐?jì)算子數(shù)組的總數(shù)哺徊，所以 Hash Table 中的鍵還是前綴和 presum，但是值要存儲(chǔ)當(dāng)前前綴和出現(xiàn)的次數(shù)乾闰，而不像前兩道題中存儲(chǔ)當(dāng)前位置索引落追。初始化時(shí)，Hash Table 中 {0: 1}涯肩，用于邊界情況處理轿钠。

舉個(gè)例子：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 中泽裳，說(shuō)明上一次出現(xiàn)前綴和 2 的位置到當(dāng)前位置之間的數(shù)字之和為 k瞒斩，則 ans += dic[7-k] = 1，并把 presum 保存在 dic = {0: 1, 2: 1, 6: 1, 7: 1}涮总；
• presum += 7胸囱，7 - k 在 dic 中，說(shuō)明上一次出現(xiàn)前綴和 2 的位置到當(dāng)前位置之間的數(shù)字之和為 k瀑梗，則 ans += dic[7-k] = 2烹笔，并把 presum 保存在 dic = {0: 1, 2: 1, 6: 1, 7: 2}（前綴和 7 之前出現(xiàn)過(guò)一次，直接累加）抛丽；
• presum += 12谤职，12 - k 在 dic 中，說(shuō)明上一次出現(xiàn)前綴和 7 的位置到當(dāng)前位置之間的數(shù)字之和為 k铺纽，則 ans += dic[12-k] = 4柬帕，并把 presum 保存在 dic = {0: 1, 2: 1, 6: 1, 7: 2, 12: 1}；
• presum += 5狡门，5 - k 在 dic 中陷寝，說(shuō)明上一次出現(xiàn)前綴和 0 的位置到當(dāng)前位置之間的數(shù)字之和為 k，則 ans += dic[5-k] = 5其馏，并把 presum 保存在 {0: 1, 2: 1, 6: 1, 7: 2, 12: 1, 5: 1}凤跑，這也是為什么初始化 Hash Table 為 {0: -1} 的原因；**
• 數(shù)組遍歷完畢叛复，ans = 5 就是答案仔引。

Python3 實(shí)現(xiàn)：

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

問(wèn)題描述：【Hash Table】974. Subarray Sums Divisible by K

解題思路：

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

經(jīng)過(guò)了上面三道題的歷練撬码，這道題自然很容易求解儿倒。題目中“連續(xù)子數(shù)組之和可以被 K 整除”類似于 Leetcode 523 的做法，要先將前綴和 presum 對(duì) K 取余呜笑，并且判斷 presum 是否在 Hash Table 中出現(xiàn)過(guò)夫否；而它是一個(gè)計(jì)算總數(shù)的問(wèn)題，類似于 Leetcode 560叫胁，Hash Table 中保存的應(yīng)該是前綴和出現(xiàn)的次數(shù)凰慈。因此，很快可以寫出代碼驼鹅。

Python3 實(shí)現(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  # 先將前綴和對(duì)K取余
            if presum in dic:
                ans += dic[presum]
            dic[presum] += 1  # 統(tǒng)計(jì)前綴和出現(xiàn)次數(shù)
        return ans

總結(jié)：

計(jì)算數(shù)組前綴（前綴和微谓、前綴01差值森篷、前綴和對(duì)K的取余結(jié)果等等）保存在 Hash Table 中，等到下次再次出現(xiàn)相同的前綴時(shí)堰酿，說(shuō)明兩次位置之間的數(shù)字是滿足題意的疾宏。利用這個(gè)特點(diǎn)张足，我們能做到在 O(n) 的時(shí)間內(nèi)求解触创。