# 560. Subarray Sum Equals K

[ **560. Subarray Sum Equals K**](https://leetcode.com/problems/subarray-sum-equals-k/description/)

Given an array of integers **nums** 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
```

**Example 2:**

```
Input: nums = [1,2,3], k = 3
Output: 2
```

**Constraints:**

* `1 <= nums.length <= 2 * 10e4`
* `-1000 <= nums[i] <= 1000`
* `-107 <= k <= 107`

***My Solutions:***

方法1：用两个for loop，对每一个数，找到所有的连续subarray

Time: O(n^2); Space: O(1)

```java
class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        
        int res = 0;
        
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) res++;
            }
        }
        return res;
    }
}
```

方法2：

在Naive的解法中，计算subarray的和的时候，每次都需要遍历该subarray中的每个数，有很多重复的计算。减少重复的一个方法，就是**把之前已经计算过的subarray(i, j)的和保存下来，当j++的时候我们只需要在原来的和的基础上加上新的nums\[j]**

比如

sum(i, j) = sum(0, j) - sum(0, i), where sum(i,j) represents the sum of all the elements from index i to j-1

prefixSum\[x] = sum of subarray(0, x) = nums\[0] + nums\[1] + ... + nums\[x]

index:               0 1 2

nums =            \[1,1,1]

prefixSum = \[0,1,2,3]

**通过这个prefixSum array，就可以用O(1)的时间求出任意一个subarray的和**

这个问题转化为 **for each j：how many i < j satisfies prefixSum\[i] = prefixSum\[j] - k.** 对于每个j，需要记录之前所有的prefixSum，然后在这些prefixSum中查找有多少个数值等于 prefixSum\[j] - k

用一个hashmap保存以下，map需要先加一个（0，1）进去，代表已经有一个可以达到presum=0的解法。

* **key：**&#x70;refixSum value
* **value：** number of occurrences of the prefixSum value

遍历数组求和，当求到一个位置的和的时候，向前找sum-k是否在map中。

* 如果sum-k在map里的，说明有subarray满足条件，count += map.get(sum - k)。
* 无论如何当前这个sum出现的次数多了一次

Time: O(n); Space: O(n)

```java
public class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        
        int count = 0, sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) count += map.get(sum - k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}
```