560. Subarray Sum Equals K

//O(n) O(n)
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> tar;
        tar[0]++;
        int sum = 0, res = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            if (tar.count(sum - k)) res += tar[sum - k];
            tar[sum]++;
        }
        return res;
    }
};

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