Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
 
Constraints:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

首先我们非常容易想到的暴力破解方法：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int element = nums.size();
        int cnt = 0;
        for(int start = 0;start < element;start++)
        {
            int sum = 0;
            for(int i = start ;i < element;i++)
            {
                sum += nums[i];
                if(sum == k)
                {
                    cnt++;
                }
            }
        }
        
        return cnt;
    }
};

复杂度n的平方，性能也如预料中一样，非常的差，差到我们只比5.01%的人快。

Runtime: 1268 ms, faster than 5.01% of C++ online submissions for Subarray Sum Equals K.
Memory Usage: 16.2 MB, less than 98.62% of C++ online submissions for Subarray Sum Equals K.

另外一种高效，但相对难想到的方法：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        std::unordered_map<int, int> seen = {{0, 1}};
        int count = 0, sum = 0;
        for (auto n: nums) {
            sum += n;
            count += seen[sum - k];
            seen[sum]++;
        }
        return count;
    }
};

性能相对方法一提升10倍，运行时间90ms左右.思路也非常奇妙，我们一直计算累加和，如果当前和减去k在前面已经求出来的累加和中，那么从那个元素之后到当前元素之间的和即为k，打完收工，睡觉大吉。