計(jì)子數(shù)組和等于 k 的個(gè)數(shù))
LeetCode 560 Subarray Sum Equals K 題解前綴和 哈希表統(tǒng)計(jì)子數(shù)組和等于 k 的個(gè)數(shù)【免費(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技術(shù)指南圍繞 LeetCode 560「和為 K 的子數(shù)組」Subarray Sum Equals K展開(kāi)完整講解從暴力枚舉到前綴和 哈希表的兩種解法、復(fù)雜度分析與常見(jiàn)陷阱并結(jié)合當(dāng)前倉(cāng)庫(kù)中 Python、C、C、Java、Go、Rust、JavaScript、TypeScript、Kotlin、Swift 等 10 種語(yǔ)言的實(shí)現(xiàn)源碼進(jìn)行印證。讀完本文你將掌握如何用 O(n) 時(shí)間統(tǒng)計(jì)和為 k 的連續(xù)子數(shù)組個(gè)數(shù)并能正確應(yīng)對(duì)負(fù)整數(shù)、k 0等邊界場(chǎng)景。前置知識(shí)在動(dòng)手解決本題之前建議先熟悉以下兩個(gè)基礎(chǔ)工具前綴和Prefix Sum最優(yōu)解依賴的核心性質(zhì)——任意子數(shù)組的和都可以由兩個(gè)前綴和相減得到。定義prefixSum[i]為數(shù)組前i個(gè)元素之和則下標(biāo)從i1到j(luò)的子數(shù)組和為prefixSum[j] - prefixSum[i]。哈希表Hash Map用于存儲(chǔ)前綴和 → 出現(xiàn)次數(shù)的映射實(shí)現(xiàn)在遍歷過(guò)程中 O(1) 查詢互補(bǔ)值curSum - k。解法一暴力枚舉Brute Force思路最樸素的做法是枚舉每一個(gè)可能的子數(shù)組檢查其和是否等于k。對(duì)每個(gè)起始下標(biāo)i我們逐元素向右擴(kuò)展子數(shù)組同時(shí)維護(hù)一個(gè)運(yùn)行中的累加和sum每當(dāng)sum k就計(jì)數(shù)一次。注意本題要求的是連續(xù)子數(shù)組因此只需要雙重循環(huán)即可覆蓋所有區(qū)間。算法步驟初始化res 0。對(duì)每個(gè)起始下標(biāo)i重置sum 0。對(duì)每個(gè)結(jié)束下標(biāo)j從i到n - 1將nums[j]累加到sum。若sum kres加一。返回res。復(fù)雜度分析時(shí)間復(fù)雜度$O(n ^ 2)$枚舉了所有 $\frac{n(n1)}{2}$ 個(gè)子數(shù)組?？臻g復(fù)雜度$O(1)$只使用了常數(shù)個(gè)變量。暴力法雖然直觀但當(dāng)n達(dá)到 $10^5$ 量級(jí)時(shí) $O(n^2)$ 必然超時(shí)因此需要更優(yōu)的解法。解法二前綴和 哈希表Hash Map思路核心洞察是若prefixSum[j] - prefixSum[i] k則從下標(biāo)i1到j(luò)的子數(shù)組和為k。于是問(wèn)題轉(zhuǎn)化為遍歷到每個(gè)位置j時(shí)統(tǒng)計(jì)此前有多少個(gè)位置i的前綴和等于curSum - k。用一個(gè)哈希表記錄每個(gè)前綴和出現(xiàn)的次數(shù)即可在 O(1) 時(shí)間內(nèi)完成查詢。算法步驟初始化res 0、curSum 0以及哈希表prefixSums并預(yù)置{0: 1}表示空前綴前綴和為 0 出現(xiàn)一次。遍歷數(shù)組中的每個(gè)數(shù)將其累加到curSum。計(jì)算diff curSum - k。將prefixSums[diff]即此前出現(xiàn)過(guò)diff這個(gè)前綴和的次數(shù)累加到res——這統(tǒng)計(jì)的是以當(dāng)前位置結(jié)尾、和為k的子數(shù)組個(gè)數(shù)。將prefixSums[curSum]加一記錄當(dāng)前前綴和。返回res。復(fù)雜度分析時(shí)間復(fù)雜度$O(n)$數(shù)組只遍歷一遍每次哈希表操作均為 O(1) 攤還?？臻g復(fù)雜度$O(n)$哈希表最多存儲(chǔ)n 1個(gè)不同的前綴和。各語(yǔ)言實(shí)現(xiàn)對(duì)照本倉(cāng)庫(kù)在 10 種語(yǔ)言中提供了該解法的實(shí)現(xiàn)核心邏輯完全一致可直接對(duì)照學(xué)習(xí)Pythonpython/0560-subarray-sum-equals-k.py 使用字典dic {0: 1}預(yù)置空前綴遍歷時(shí)先查sum - k再更新dic[sum]并注明 O(N) 時(shí)間、O(N) 空間。Ccpp/0560-subarray-sum-equals-k.cpp 使用unordered_mapint,int注意其額外在sum target時(shí)直接對(duì)count加一與mp[sum - target]的統(tǒng)計(jì)邏輯等價(jià)因?yàn)閙p[0]尚未初始化時(shí)默認(rèn)計(jì)數(shù)缺失需依賴預(yù)置的mp[0]實(shí)際上該實(shí)現(xiàn)以sum target顯式補(bǔ)上從下標(biāo) 0 開(kāi)始的子數(shù)組這一情況。Cc/0560-subarray-sum-equals-k.c 展示了不依賴標(biāo)準(zhǔn)庫(kù)哈希表時(shí)的完整手寫(xiě)實(shí)現(xiàn)定義Hash鏈地址法結(jié)構(gòu)體INIT_HASH_SIZE 4096作為桶數(shù)HashKey通過(guò)取模把負(fù)前綴和歸一化到桶內(nèi)AddHash處理沖突、GetHash未命中返回 0主函數(shù)subarraySum同樣先AddHash(hash, 0)預(yù)置空前綴再先查后插。這段代碼對(duì)理解哈希表底層原理很有價(jià)值。Javajava/0560-subarray-sum-equals-k.java 使用HashMapInteger, IntegergetOrDefault(diff, 0)處理缺失鍵。Gogo/0560-subarray-sum-equals-k.go 用字面量map[int]int{0: 1}初始化。Rustrust/0560-subarray-sum-equals-k.rs 用HashMap::with_capacity(nums.len() / 2)預(yù)分配容量entry(...).and_modify(...).or_insert(1)完成計(jì)數(shù)更新。JavaScriptjavascript/0560-subarray-sum-equals-k.js 與TypeScripttypescript/0560-subarray-sum-equals-k.ts 使用Map以map.get(sum) || 0處理缺省值。Kotlinkotlin/0560-subarray-sum-equals-k.kt 使用hashMapOf(0 to 1)與getOrDefault。Swiftswift/0560-subarray-sum-equals-k.swift 使用字典[0: 1]與hashmap[diff, default: 0]。從上述實(shí)現(xiàn)可以看到無(wú)論語(yǔ)言如何算法骨架完全一致預(yù)置{0: 1}→ 累加curSum→ 查詢curSum - k→ 更新curSum計(jì)數(shù)。常見(jiàn)陷阱Common Pitfalls陷阱一忘記用零初始化哈希表哈希表必須以{0: 1}作為初始狀態(tài)用于處理從下標(biāo) 0 開(kāi)始的子數(shù)組。如果沒(méi)有這一初始化那么從頭開(kāi)始的、前綴和恰好等于k的子數(shù)組將永遠(yuǎn)無(wú)法被計(jì)數(shù)。例如nums [3, 4, 7, 2]、k 7遍歷到下標(biāo) 1 時(shí)curSum 7需要diff 0存在才會(huì)計(jì)數(shù)[3, 4]這個(gè)子數(shù)組{0: 1}正是提供這個(gè)基準(zhǔn)。陷阱二試圖使用滑動(dòng)窗口Sliding Window與乘積小于 K 的子數(shù)組這類單調(diào)性問(wèn)題不同本題數(shù)組允許出現(xiàn)負(fù)數(shù)運(yùn)行中的累加和并不單調(diào)收縮窗口可能讓和變大也可能變小無(wú)法確定性地維護(hù)窗口。因此滑動(dòng)窗口在這里失效必須采用前綴和 哈希表的方案。陷阱三先更新哈希表再查詢操作的順序至關(guān)重要必須先檢查curSum - k是否在哈希表中然后再把curSum寫(xiě)入哈希表。若順序顛倒當(dāng)前元素會(huì)被錯(cuò)誤地當(dāng)作之前出現(xiàn)過(guò)的前綴和參與計(jì)數(shù)導(dǎo)致統(tǒng)計(jì)偏差。以k 0的場(chǎng)景為例若先寫(xiě)入curSum再查詢curSum - 0 curSum會(huì)把空子數(shù)組也計(jì)入結(jié)果得到錯(cuò)誤答案。舉一反三邊界與變式k 0且數(shù)組含零nums [1, -1, 0]、k 0時(shí)正確答案為 3子數(shù)組[1, -1]、[0]、[1, -1, 0]。用哈希表方案手工推演一遍即可驗(yàn)證{0: 1}初始化與先查后插順序的必要性。答案上限子數(shù)組個(gè)數(shù)最多為 $\frac{n(n1)}{2}$當(dāng)數(shù)組元素全為 0 且k 0時(shí)達(dá)到該上限因此res在 LeetCode 約束下需用int表示Python 無(wú)此顧慮。變式延伸同一套前綴和 哈希表思路稍加改造即可遷移到 subarray-sums-divisible-by-k改為對(duì)k取模、continuous-subarray-sum查找長(zhǎng)度 ≥ 2 的倍數(shù)子數(shù)組等題目值得一并練習(xí)。小結(jié)解法時(shí)間復(fù)雜度空間復(fù)雜度適用場(chǎng)景暴力枚舉$O(n^2)$$O(1)$數(shù)組規(guī)模小、僅用于理解題意前綴和 哈希表$O(n)$$O(n)$大規(guī)模數(shù)組含負(fù)數(shù)標(biāo)準(zhǔn)解法Subarray Sum Equals K 是前綴和 哈希表這一經(jīng)典組合的入門(mén)必刷題它把一個(gè)看似需要枚舉所有子數(shù)組的問(wèn)題轉(zhuǎn)化為統(tǒng)計(jì)互補(bǔ)前綴和出現(xiàn)次數(shù)的線性掃描問(wèn)題。掌握{(diào)0: 1}初始化、先查詢后更新這兩個(gè)關(guān)鍵點(diǎn)并理解為什么負(fù)數(shù)使滑動(dòng)窗口失效你就真正吃透了這道題也能為后續(xù)的子數(shù)組類問(wèn)題打下堅(jiān)實(shí)基礎(chǔ)?！久赓M(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 LeetCode 560 Subarray Sum Equals K 題解：前綴和 + 哈希表統(tǒng)計(jì)子數(shù)組和等于 k 的個(gè)數(shù)
LeetCode 560 Subarray Sum Equals K 題解前綴和 哈希表統(tǒng)計(jì)子數(shù)組和等于 k 的個(gè)數(shù)【免費(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技術(shù)指南圍繞 LeetCode 560「和為 K 的子數(shù)組」Subarray Sum Equals K展開(kāi)完整講解從暴力枚舉到前綴和 哈希表的兩種解法、復(fù)雜度分析與常見(jiàn)陷阱并結(jié)合當(dāng)前倉(cāng)庫(kù)中 Python、C、C、Java、Go、Rust、JavaScript、TypeScript、Kotlin、Swift 等 10 種語(yǔ)言的實(shí)現(xiàn)源碼進(jìn)行印證。讀完本文你將掌握如何用 O(n) 時(shí)間統(tǒng)計(jì)和為 k 的連續(xù)子數(shù)組個(gè)數(shù)并能正確應(yīng)對(duì)負(fù)整數(shù)、k 0等邊界場(chǎng)景。前置知識(shí)在動(dòng)手解決本題之前建議先熟悉以下兩個(gè)基礎(chǔ)工具前綴和Prefix Sum最優(yōu)解依賴的核心性質(zhì)——任意子數(shù)組的和都可以由兩個(gè)前綴和相減得到。定義prefixSum[i]為數(shù)組前i個(gè)元素之和則下標(biāo)從i1到j(luò)的子數(shù)組和為prefixSum[j] - prefixSum[i]。哈希表Hash Map用于存儲(chǔ)前綴和 → 出現(xiàn)次數(shù)的映射實(shí)現(xiàn)在遍歷過(guò)程中 O(1) 查詢互補(bǔ)值curSum - k。解法一暴力枚舉Brute Force思路最樸素的做法是枚舉每一個(gè)可能的子數(shù)組檢查其和是否等于k。對(duì)每個(gè)起始下標(biāo)i我們逐元素向右擴(kuò)展子數(shù)組同時(shí)維護(hù)一個(gè)運(yùn)行中的累加和sum每當(dāng)sum k就計(jì)數(shù)一次。注意本題要求的是連續(xù)子數(shù)組因此只需要雙重循環(huán)即可覆蓋所有區(qū)間。算法步驟初始化res 0。對(duì)每個(gè)起始下標(biāo)i重置sum 0。對(duì)每個(gè)結(jié)束下標(biāo)j從i到n - 1將nums[j]累加到sum。若sum kres加一。返回res。復(fù)雜度分析時(shí)間復(fù)雜度$O(n ^ 2)$枚舉了所有 $\frac{n(n1)}{2}$ 個(gè)子數(shù)組?？臻g復(fù)雜度$O(1)$只使用了常數(shù)個(gè)變量。暴力法雖然直觀但當(dāng)n達(dá)到 $10^5$ 量級(jí)時(shí) $O(n^2)$ 必然超時(shí)因此需要更優(yōu)的解法。解法二前綴和 哈希表Hash Map思路核心洞察是若prefixSum[j] - prefixSum[i] k則從下標(biāo)i1到j(luò)的子數(shù)組和為k。于是問(wèn)題轉(zhuǎn)化為遍歷到每個(gè)位置j時(shí)統(tǒng)計(jì)此前有多少個(gè)位置i的前綴和等于curSum - k。用一個(gè)哈希表記錄每個(gè)前綴和出現(xiàn)的次數(shù)即可在 O(1) 時(shí)間內(nèi)完成查詢。算法步驟初始化res 0、curSum 0以及哈希表prefixSums并預(yù)置{0: 1}表示空前綴前綴和為 0 出現(xiàn)一次。遍歷數(shù)組中的每個(gè)數(shù)將其累加到curSum。計(jì)算diff curSum - k。將prefixSums[diff]即此前出現(xiàn)過(guò)diff這個(gè)前綴和的次數(shù)累加到res——這統(tǒng)計(jì)的是以當(dāng)前位置結(jié)尾、和為k的子數(shù)組個(gè)數(shù)。將prefixSums[curSum]加一記錄當(dāng)前前綴和。返回res。復(fù)雜度分析時(shí)間復(fù)雜度$O(n)$數(shù)組只遍歷一遍每次哈希表操作均為 O(1) 攤還?？臻g復(fù)雜度$O(n)$哈希表最多存儲(chǔ)n 1個(gè)不同的前綴和。各語(yǔ)言實(shí)現(xiàn)對(duì)照本倉(cāng)庫(kù)在 10 種語(yǔ)言中提供了該解法的實(shí)現(xiàn)核心邏輯完全一致可直接對(duì)照學(xué)習(xí)Pythonpython/0560-subarray-sum-equals-k.py 使用字典dic {0: 1}預(yù)置空前綴遍歷時(shí)先查sum - k再更新dic[sum]并注明 O(N) 時(shí)間、O(N) 空間。Ccpp/0560-subarray-sum-equals-k.cpp 使用unordered_mapint,int注意其額外在sum target時(shí)直接對(duì)count加一與mp[sum - target]的統(tǒng)計(jì)邏輯等價(jià)因?yàn)閙p[0]尚未初始化時(shí)默認(rèn)計(jì)數(shù)缺失需依賴預(yù)置的mp[0]實(shí)際上該實(shí)現(xiàn)以sum target顯式補(bǔ)上從下標(biāo) 0 開(kāi)始的子數(shù)組這一情況。Cc/0560-subarray-sum-equals-k.c 展示了不依賴標(biāo)準(zhǔn)庫(kù)哈希表時(shí)的完整手寫(xiě)實(shí)現(xiàn)定義Hash鏈地址法結(jié)構(gòu)體INIT_HASH_SIZE 4096作為桶數(shù)HashKey通過(guò)取模把負(fù)前綴和歸一化到桶內(nèi)AddHash處理沖突、GetHash未命中返回 0主函數(shù)subarraySum同樣先AddHash(hash, 0)預(yù)置空前綴再先查后插。這段代碼對(duì)理解哈希表底層原理很有價(jià)值。Javajava/0560-subarray-sum-equals-k.java 使用HashMapInteger, IntegergetOrDefault(diff, 0)處理缺失鍵。Gogo/0560-subarray-sum-equals-k.go 用字面量map[int]int{0: 1}初始化。Rustrust/0560-subarray-sum-equals-k.rs 用HashMap::with_capacity(nums.len() / 2)預(yù)分配容量entry(...).and_modify(...).or_insert(1)完成計(jì)數(shù)更新。JavaScriptjavascript/0560-subarray-sum-equals-k.js 與TypeScripttypescript/0560-subarray-sum-equals-k.ts 使用Map以map.get(sum) || 0處理缺省值。Kotlinkotlin/0560-subarray-sum-equals-k.kt 使用hashMapOf(0 to 1)與getOrDefault。Swiftswift/0560-subarray-sum-equals-k.swift 使用字典[0: 1]與hashmap[diff, default: 0]。從上述實(shí)現(xiàn)可以看到無(wú)論語(yǔ)言如何算法骨架完全一致預(yù)置{0: 1}→ 累加curSum→ 查詢curSum - k→ 更新curSum計(jì)數(shù)。常見(jiàn)陷阱Common Pitfalls陷阱一忘記用零初始化哈希表哈希表必須以{0: 1}作為初始狀態(tài)用于處理從下標(biāo) 0 開(kāi)始的子數(shù)組。如果沒(méi)有這一初始化那么從頭開(kāi)始的、前綴和恰好等于k的子數(shù)組將永遠(yuǎn)無(wú)法被計(jì)數(shù)。例如nums [3, 4, 7, 2]、k 7遍歷到下標(biāo) 1 時(shí)curSum 7需要diff 0存在才會(huì)計(jì)數(shù)[3, 4]這個(gè)子數(shù)組{0: 1}正是提供這個(gè)基準(zhǔn)。陷阱二試圖使用滑動(dòng)窗口Sliding Window與乘積小于 K 的子數(shù)組這類單調(diào)性問(wèn)題不同本題數(shù)組允許出現(xiàn)負(fù)數(shù)運(yùn)行中的累加和并不單調(diào)收縮窗口可能讓和變大也可能變小無(wú)法確定性地維護(hù)窗口。因此滑動(dòng)窗口在這里失效必須采用前綴和 哈希表的方案。陷阱三先更新哈希表再查詢操作的順序至關(guān)重要必須先檢查curSum - k是否在哈希表中然后再把curSum寫(xiě)入哈希表。若順序顛倒當(dāng)前元素會(huì)被錯(cuò)誤地當(dāng)作之前出現(xiàn)過(guò)的前綴和參與計(jì)數(shù)導(dǎo)致統(tǒng)計(jì)偏差。以k 0的場(chǎng)景為例若先寫(xiě)入curSum再查詢curSum - 0 curSum會(huì)把空子數(shù)組也計(jì)入結(jié)果得到錯(cuò)誤答案。舉一反三邊界與變式k 0且數(shù)組含零nums [1, -1, 0]、k 0時(shí)正確答案為 3子數(shù)組[1, -1]、[0]、[1, -1, 0]。用哈希表方案手工推演一遍即可驗(yàn)證{0: 1}初始化與先查后插順序的必要性。答案上限子數(shù)組個(gè)數(shù)最多為 $\frac{n(n1)}{2}$當(dāng)數(shù)組元素全為 0 且k 0時(shí)達(dá)到該上限因此res在 LeetCode 約束下需用int表示Python 無(wú)此顧慮。變式延伸同一套前綴和 哈希表思路稍加改造即可遷移到 subarray-sums-divisible-by-k改為對(duì)k取模、continuous-subarray-sum查找長(zhǎng)度 ≥ 2 的倍數(shù)子數(shù)組等題目值得一并練習(xí)。小結(jié)解法時(shí)間復(fù)雜度空間復(fù)雜度適用場(chǎng)景暴力枚舉$O(n^2)$$O(1)$數(shù)組規(guī)模小、僅用于理解題意前綴和 哈希表$O(n)$$O(n)$大規(guī)模數(shù)組含負(fù)數(shù)標(biāo)準(zhǔn)解法Subarray Sum Equals K 是前綴和 哈希表這一經(jīng)典組合的入門(mén)必刷題它把一個(gè)看似需要枚舉所有子數(shù)組的問(wèn)題轉(zhuǎn)化為統(tǒng)計(jì)互補(bǔ)前綴和出現(xiàn)次數(shù)的線性掃描問(wèn)題。掌握{(diào)0: 1}初始化、先查詢后更新這兩個(gè)關(guān)鍵點(diǎn)并理解為什么負(fù)數(shù)使滑動(dòng)窗口失效你就真正吃透了這道題也能為后續(xù)的子數(shù)組類問(wèn)題打下堅(jiān)實(shí)基礎(chǔ)?！久赓M(fèi)下載鏈接】leetcodeLeetcode solutions項(xiàng)目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考