560. Subarray Sum Equals K --------M

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

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

A:

--------就是按照 和的长度，一个个加起来，看是否是结果。

-------------这个用的空间最小----------------

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int res = 0;
        vector<int> curSum(n,0);
        for(int curLen = 1; curLen <= n; curLen++)
        {
            for(int i = 0; i+curLen <= n; ++i)
            {
                curSum[i] += nums[i+curLen-1];
                if(curSum[i] == k)
                    ++res;
            }
        }
        return res;
    }
};

------------------------ 这个最快--------------

class Solution {

public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> m = {{0, 1}}; // initialize with m[0] = 1
        int count = 0, sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (m.find(sum - k) != m.end()) {
                count += m[sum - k];
            }
            m[sum]++;
        }
        return count;
    }
};