# 0560. 和為K的子數組 ## 題目地址(560. 和為K的子數組) <https://leetcode-cn.com/problems/subarray-sum-equals-k/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個整數數組和一個整數 k，你需要找到該數組中和為 k 的連續的子數組的個數。 示例 1 : 輸入:nums = [1,1,1], k = 2 輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況。 說明 : 數組的長度為 [1, 20,000]。 數組中元素的范圍是 [-1000, 1000] ，且整數 k 的范圍是 [-1e7, 1e7]。 ``` ``` ## 前置知識 - 哈希表 - 前綴和 ## 公司 - 阿里 - 騰訊 - 字節 ## 思路 符合直覺的做法是暴力求解所有的子數組，然后分別計算和，如果等于 k,count 就+1.這種做法的時間復雜度為 O(n^2)，代碼如下： ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subarraySum</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -> int:</span> cnt, n = <span class="hljs-params">0</span>, len(nums) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): sum = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i, n): sum += nums[j] <span class="hljs-keyword">if</span> (sum == k): cnt += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> cnt ``` ``` 實際上剛開始看到這題目的時候，我想“是否可以用滑動窗口解決？”。但是很快我就放棄了，因為看了下數組中項的取值范圍有負數，這樣我們擴張或者收縮窗口就比較復雜。第二個想法是前綴和，保存一個數組的前綴和，然后利用差分法得出任意區間段的和，這種想法是可行的，代碼如下： ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subarraySum</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -> int:</span> cnt, n = <span class="hljs-params">0</span>, len(nums) pre = [<span class="hljs-params">0</span>] * (n + <span class="hljs-params">1</span>) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>): pre[i] = pre[i - <span class="hljs-params">1</span>] + nums[i - <span class="hljs-params">1</span>] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i, n + <span class="hljs-params">1</span>): <span class="hljs-keyword">if</span> (pre[j] - pre[i - <span class="hljs-params">1</span>] == k): cnt += <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> cnt ``` ``` 這里有一種更加巧妙的方法，可以不使用前綴和數組，而是使用 hashmap 來簡化時間復雜度，這種算法的時間復雜度可以達到 O(n). 具體算法： - 維護一個 hashmap，hashmap 的 key 為累加值 acc，value 為累加值 acc 出現的次數。 - 迭代數組，然后不斷更新 acc 和 hashmap，如果 acc 等于 k，那么很明顯應該+1. 如果 hashmap\[acc - k\] 存在，我們就把它加到結果中去即可。 語言比較難以解釋，我畫了一個圖來演示 nums = \[1,2,3,3,0,3,4,2\], k = 6 的情況。  如圖，當訪問到 nums\[3\]的時候，hashmap 如圖所示，這個時候 count 為 2. 其中之一是\[1,2,3\],這個好理解。還有一個是\[3,3\]. 這個\[3,3\]正是我們通過 hashmap\[acc - k\]即 hashmap\[9 - 6\]得到的。 ## 關鍵點解析 - 前綴和 - 可以利用 hashmap 記錄和的累加值來避免重復計算 ## 代碼 - 語言支持：JS, Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=560 lang=javascript * * [560] Subarray Sum Equals K */</span> <span class="hljs-title">/** * @param {number[]} nums * @param {number} k * @return {number} */</span> <span class="hljs-keyword">var</span> subarraySum = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums, k</span>) </span>{ <span class="hljs-keyword">const</span> hashmap = {}; <span class="hljs-keyword">let</span> acc = <span class="hljs-params">0</span>; <span class="hljs-keyword">let</span> count = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { acc += nums[i]; <span class="hljs-keyword">if</span> (acc === k) count++; <span class="hljs-keyword">if</span> (hashmap[acc - k] !== <span class="hljs-keyword">void</span> <span class="hljs-params">0</span>) { count += hashmap[acc - k]; } <span class="hljs-keyword">if</span> (hashmap[acc] === <span class="hljs-keyword">void</span> <span class="hljs-params">0</span>) { hashmap[acc] = <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> { hashmap[acc] += <span class="hljs-params">1</span>; } } <span class="hljs-keyword">return</span> count; }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">subarraySum</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -> int:</span> d = {} acc = count = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums: acc += num <span class="hljs-keyword">if</span> acc == k: count += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> acc - k <span class="hljs-keyword">in</span> d: count += d[acc-k] <span class="hljs-keyword">if</span> acc <span class="hljs-keyword">in</span> d: d[acc] += <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: d[acc] = <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> count ``` ``` ## 擴展 這是一道類似的題目，但是會稍微復雜一點, 題目地址: [437.path-sum-iii](437.path-sum-iii.html)