Subarray Sum Equals K

• Lintcode : 838
• Level : Easy

Problem

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
Example1

Input: nums = [1,1,1] and k = 2
Output: 2
Explanation:
subarray [0,1] and [1,2]
Example2

Input: nums = [2,1,-1,1,2] and k = 3
Output: 4
Explanation:
subarray [0,1], [1,4], [0,3] and [3,4]

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n)
space: O(n)

Answer

/*
// TLE
class Solution {
public:
    int subarraySumEqualsK(vector<int> &nums, int k) {
        if (nums.size() == 0) return 0;
        vector<int> prefix;
        int sum = 0;
        prefix.push_back(sum);
        for (auto i : nums) {
            sum += i;
            prefix.push_back(sum);
        }
        int count = 0;
        for (int i = 1; i < prefix.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (prefix[i] - prefix[j] == k) count++;
            }
        }
        return count;
    }
};
*/

class Solution {
public:
    int subarraySumEqualsK(vector<int> &nums, int k) {
        for (int i = 1; i < nums.size(); i++) {
            nums[i] += nums[i - 1];
        }
        map<int, int> map;
        int count = 0;
        map[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            count += map[nums[i] - k];
            map[nums[i]]++;
        }
        return count;
    }
};

tags: other

​