前言

今天這題也是來自top 100 liked的題目，題目是：560. Subarray Sum Equals K，個人認為這題運用的解法真的可以非常巧妙！學起來後面有相似題目受用無窮~

想法

一開始在解這題的時候，真的是在苦惱之後解出又慢又醜的解，然後在研究官方解答時從 Approach 1 ~ Approach 4，看到最後巧秒的解跟前面的解反差很大，深受震撼，這套解法就深深烙印在腦海中了~
不過我們還是先按照官方解順序分析這題的各種方式，最後看到厲害的解法才會印象深刻XD。
如果想直接看厲害的解可以直接拉到Approach 4。

Approach 1: Brute Force

當不知道怎麼下手的時候，先來個暴力解是很自然的事情，至少要有個合理的解法，再來思考怎麼優化。
既然要取subarray，那暴力的方法就是找到所有頭尾組合，時間複雜度花費是O(n^2)，然後再把裡面的元素加總，花費O(n)，所以時間複雜度總共就是相乘O(n^3)，想當然，會超時~

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans=0;
        // i for head
        for(int i=0; i<nums.size();++i){
            // j for end
            for(int j=i;j<nums.size();++j){
                // compute sum
                int sum=0;
                for(int n=i;n<=j;++n){
                    sum+=nums[n];
                }
                if(sum==k){
                    ++ans;
                }
            }
        }
        return ans;
    }
};

Approach 2: Using Cumulative Sum

要怎麼把 approach 1 優化呢？我們可以朝最後加總的那段下手。因為approach 1我們窮舉完頭尾之後，加總我們都重新計算一次。使用cumulative sum的話，我們可以把計算加總的O(n)計算變成直接拿尾端的cumulative sum-頭的cumulative sum變成O(1)的計算，整個複雜度就優化為O(n^2)了，而空間複雜度因要儲存cumulative sum是O(n)。
不過，還是超時QQ

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans=0;
        vector<int> cum(nums.size()+1);
        // compute for cumulative sum first
        for(int i=1; i<=nums.size(); ++i){
            cum[i] = cum[i-1]+nums[i-1];
        }
        // i for head
        for(int i=0; i<nums.size();++i){
            // j for end
            for(int j=i;j<nums.size();++j){
                // compute sum
                if((cum[j+1]-cum[i])==k){
                    ++ans;
                }
            }
        }
        return ans;
    }
};

Approach 3: Without Space

再接再厲~這次優化的是空間複雜度。
其實這個解法應該算是跟Approach2平行的解法，一樣是改良Approach1。我們不用每次重新計算該段的sum，因為我們在變動end的時候其實跟前一個組合只差了nums[j]的那個數字，
這個解基本上跟Approach 2的時間複雜度也一樣，是O(n^2)，不用先遍歷一次儲存累積sum，而是每次把前面的結果拿來做一個+的計算，空間複雜度O(1)。一樣超時。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans=0;
        // i for head
        for(int i=0; i<nums.size();++i){
            // sum for same start point
            int sum=0;
            // j for end
            for(int j=i;j<nums.size();++j){
                // compute sum by difference
                sum+=nums[j];
                if(sum==k){
                    ++ans;
                }
            }
        }
        return ans;
    }
};

Approach 4: Using Hashmap

重頭戲來了，我們可以直接達到O(n)複雜度。O(n)代表我們只需要遍歷整個vector一次！要怎麼達到呢？
其實運用的還是cumulative sum的概念。關鍵在於把cumulative sum存成hash map，hash map的內容物為目前的cumulative sum與對應的次數。例如：[1,1,2,3]，target是2，首先hashmap我們存入hm[0]=1，代表說目前累積sum=0的情況有一種(就是什麼都不取)；遍歷第一個的時候，目前的累積curSum=1，因此我們回過頭去檢查hm[curSum-target]=hm[1-2]=hm[-1]有幾個？因為我們需要前面的加總是-1，這樣1-(-1)才會=我們要的target。而我們查到hm[-1]=0，並沒有這個cumulative sum存在，我們就繼續把hashmap中hm[1]++，代表目前cumulative sum=1的有1個。
而我們持有這個累積sum繼續算下一個，現在curSum=2，回去檢查hm[curSum-target]=hm[2-2]=hm[0]，發現=1，因此解答+1個；繼續把hashmap中hm[2]++，代表目前cumulative sum=2的多了一個。
到第三個數的時候，現在curSum=4，回去檢查hm[curSum-target]=hm[4-2]=hm[2]，發現=1，因此解答+1個；繼續把hashmap中hm[4]++，代表目前cumulative sum=4的多了一個....以此類推。
而我們在遍歷的時候，就像是在遍歷subarray尾端，藉由hashmap直接去找，有幾個對應的頭端可以相減出target sum？就可以算出這個尾端有幾個subarray可以達到這個target sum。
可以參考官方解答提供的動畫。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans=0;
        int curSum=0;
        // record the cumulative sum count
        unordered_map<int, int> hm;
        hm[0]=1;
        for(int i=0; i<nums.size();++i){
            curSum+=nums[i];
            // compute how many subarray ends with nums[i]
            ans+=hm[curSum-k];
            // add current curSum
            ++hm[curSum];
        }
        return ans;
    }
};

時間複雜度為O(n)，而空間複雜度為O(n)，需要存入那個hash map。

結語

進入最後1/3啦！不過活動結束之後還是會持續解題的，只是發文動力可能大為降低XD
另外今天這題在top 100 liked problems裡面也有非常類似可以延伸運用的一題：437. Path Sum III，可以挑戰看看！又多了binary tree跟function的概念，或明天就來解這題XD