### 题目

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:

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

### 朴素预求和，$O(n^2)$

#### 代码

class Solution {
public int subarraySum(int[] nums, int k) {
for (int i = 1; i < nums.length; i++) {
nums[i] = nums[i-1] + nums[i];
}
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
int sum = nums[j] - ((i == 0)? 0 : nums[i-1]);
if (sum == k) { count++; }
}
}
return count;
}
}


### 用一个Map储存预求和的结果，$O(n)$

#### 代码

class Solution {
public int subarraySum(int[] nums, int k) {
int res = 0;
int sum = 0;
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
res += map.getOrDefault(sum - k,0);
map.put(sum,map.getOrDefault(sum,0)+1);
}
return res;
}
}