[Day 21] Leetcode 560. Subarray Sum Equals K (C++)

前言

今天这题也是来自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