Problem statement:

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 = 2Output: 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].

Solution: two level loop(AC), I am surprised it is accepted.

The question comes from leetcode weekly contest 30. I solved it with a two level loop and it is accepted by OJ. It gave me the time is 379ms. Time complexity is O(n * n). I am very surprised that OJ accepted O(n * n) solution. But AC is not the end, Let`s optimize it!

Time complexity is O(n * n), space complexity is O(1).

class Solution {public:    int subarraySum(vector<int>& nums, int k) {        int cnt = 0;        for(vector<int>::size_type ix = 0; ix < nums.size(); ix++){            int sum = 0;            for(vector<int>::size_type iy = ix; iy < nums.size(); iy++){                sum += nums[iy];                if(sum == k){                    cnt++;                }            }        }        return cnt;    }};

Solution two: prefix sum + hash table(AC)

But AC is not the end, Let`s optimize it!

It comes from Leetcode article. The key is also prefix sum. And also, it normally increases the space complexity for the reduction of time complexity. Similar problem: 523. Continuous Subarray Sum.

The basic idea:

• A hash table to put all prefix sum and the count of this sum. If two index i and j get the sum prefix sum, that means the sum between i and j is 0. The initialization of hash table is {0, 1} since the sum is 0 if we do nothing for the array.
• Traverse from beginning to the end, for the prefix sum in i, we index by sum - k from hash table, and add the count of sum - k to final answer if it exists in hash table.

Time complexity is O(n). Space complexity is O(n).

class Solution {public:    int subarraySum(vector<int>& nums, int k) {        unordered_map<int, int> hash_table{{0, 1}}; // <sum, # of sum>        int sum = 0;        int cnt = 0;        for(auto num : nums){            sum += num;            if(hash_table.count(sum - k)){                cnt += hash_table[sum - k];            }            hash_table[sum]++;        }        return cnt;     }};

560. Subarray Sum Equals K