描述：给定一个整数数组和一个整数k，找到数组中和为k的连续子数组的个数。
    Description: 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:
    Input: nums = [1, 1, 1], k = 3; output: 1
    Constrains:

    • The length of the array is in range of [1, 20000]
    • The range of number in array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7]。

    Tips: PreFix-Sum, Hash-Map,

    思路：连续子数组的和与连续子数组的和仍然是连续子数组；

    方法1：采用枚举方法， PreFix-Sum[i]表示前i个数组元素和，遍历[0, i-1]之间的j元素，存在PreFix-Sum[i] - PreFix-Sum[j] == k，在表示存在一个和为k的子数组。
    改进：如果提前计算出全部的PreFix-Sum，则需要额外的空间O(n)和时间O(n); 这里采用在for(j in [0, i-1])的时候开始从后往前计算累加和sum, 如果sum == k表明存在一个和为k的子数组。

    1. int subarraySum(vector<int> &nums, int k)
    2. {
    3.     int nums_size = nums.size();
    4.     int counts = 0;
    5.     for(int i = 0; i<nums_size; ++i)
    6.     {
    7.         int sum = 0;
    8.         for(int j=i; j>=0; --j)
    9.         {
    10.             sum += nums[j];         // 从后往前加
    11.             if (sum == k)
    12.                 counts++;
    13.         }
    14.     }
    15.     return counts;
    16. }

    时间复杂度：O(n^2), 空间复杂度O(1)

    方法2：从方法1中可以看到，每个i都需要重新开始从j处从尾到头的计算sum, 这样存在重复计算；而且针对PreFix-Sum, i从前往后遍历的过程中，如果在i出存在sum - k存在过(采用一个哈希表记录， count表示出现的次数)， 说明在i之前出现过连续子数组和为sum-k。由于PreFix-Sum[i]也是连续的，所以说明存在count个和为k的连续子数组。
    WeChat Image_20200515122457.jpg
    原理示意图

    int subarraySum(vector<int> &nums, int k)
{
    int nums_size = nums.size();
    unordered_map<int, int> hash_map; // <key, count>
    hash_map[0] = 1;                  // 如果sum == k, 表明整个子数组满足要求
    int sum = 0;
    int counts = 0;
    for(auto & num : nums)            // C++11
    {
        sum += num;
        counts += hash_map[sum - k];  // 存在和为sum-k的子数组
        ++hash_map[sum];
    }
    return counts;
}

    时间复杂度：O(n), 空间复杂度：O(n)hash_map