先一起來看看題目：
題目描述
Given an array of integers and an integer k, you need to find the total number of contiguous subarrays whose sum equals to k.
Example 1:
Input: nums = [1,1,1], k = 2Output: 2
[1, 1, 1]
[1, 1, 1]
考點解析
在面試中我們經常會碰到一類問題，跟input array中的所有subarray sum相關。
在這類題目中，我們可以使用到一個非常常見的precomputation的方法來進行優化：prefixSum array。
今天的習題講解，我們就重點講解一下：
如何利用prefixSum array的思想，非常有效的解決Subarray Sum Equals K這個問題。
接下來，我們有請閆老師為我們詳解這道題的答案：
主講人：閆老師
來Offer金牌老師
前Google資深程序員、面試官
Google連續多年top performer
解題思路
在這道題目中，閆老師講解了三個不同的解法，從最naive的解法，到optimize的解法。並一步步講解本題的優化過程。
解法1：Naive Solution
拿到題目，我們很快就能想到的一個最直接的方法：
找到input array的所有可能的subarray，然後判斷每個subarray的和是否與k相等。
一個比較暴力的方法，就是用三層for loop，找到所有可能的subarray，並遍歷subarray中的每個數，計算subarray的和。
解法2：Better Solution
從上一個解法出發，我們能看到一個比較明顯的優化就是減少重複計算。
在Naive的解法中，在計算subarray的和的時候，我們每次都需要遍歷該subarray中的每個數。實際上，這是有很多重複的。
以subarray(i, j)為例（i為subarray的起點，j為終點）：
當i = 0，j = 1的時候，需要遍歷nums[0], nums[1]。
當i = 0, j = 2的時候，需要遍歷nums[0], nums[1], nums[2]。
顯然，前兩個數字被遍歷了多次。圖中藍色部分為重複遍歷的元素。
那麼，減少重複的一個方法，就是把之前已經計算過的subarray(i, j)的和保存下來，當j++的時候我們只需要在原來的和的基礎上加上新的nums[j]，來達到減少重複遍歷的目的，也降低了時間複雜度。
解法3：Linear Solution
進一步優化，我們會用到一個非常重要的precomputation的技巧：prefixSum array。
prefixSum array的每一個index所對應的value，和最開始的input array有一個對應關係：
通過這個prefixSum array，我們就可以用O(1)的時間求出任意一個subarray的和：
sum of subarray(i, j) = prefixSum[j] - prefixSum[i - 1]
注意上圖中紅色的0，是為了解決當i == 0的時候的subarray(i, j)的和，這時對應的prefixSum[i - 1]應該是0
有了prefixSum array，這個問題就轉化成了
for each j：how many i < j satisfies prefixSum[i] = prefixSum[j] - k
這意味著對於每個j，我們需要記錄之前所有的prefixSum，然後在這些prefixSum中查找有多少個數值 == prefixSum[j] - k。
這是一個look up的操作，為了更加有效的解決這個問題，我們可以使用一個HashMap：
key：prefixSum value
value：number of occurence of the prefixSum value。
在實際實現中，我們發現，在從左到右遍歷整個array過程中，我們可以只需要一個prefixSum的variable 來依次計算所有的prefixSum值，並將其存入HashMap中，無需提前計算出整個prefixSum array。
代碼實現
算法與代碼中需要注意的細節處理及時間、空間複雜度分析請觀看視頻講解。
E/N/D
更多科技求職資訊，請關注“來Offer”
閱讀更多 LaiOffer來Offer 的文章
