LeetCode 560. Subarray Sum Equals K

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].

解析：计算子数组的和等于K的所有子数组数量。首先考虑暴力法，两层循环，时间复杂度为\(O(N^2)\)。那需要进行时间复杂度的优化，采用空间换时间的思路。使用一个hashmap存放所有子数组的和，然后从开始元素遍历，用sum存放元素累加和，然后判断sum-k是否在hashmap中。另外需要注意的是如果sum=k，则sum-k=0.所有初始化hashmap的时候需要针对0做个特殊处理。代码如下：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int result = 0;
        unordered_map<int, int> cache;
        int len = nums.size();
        int sum = 0;
        cache[0] = 1;
        for(int i=0; i < len; i++)
        {
            sum += nums[i];
            if(cache.find(sum-k) != cache.end())
                result += cache[sum-k];
            cache[sum] += 1;
        }
        return result; 
    }
};