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

解法一：利用sum之间的差暴力搜索

class Solution {    public int subarraySum(int[] nums, int k) {        if (nums == null || nums.length == 0)            return 0;        int len = nums.length;        int[] sum = new int[len+1];        for (int i=0; i

解法二：利用map建立sum和出现次数cnt的映射关系

class Solution {    public int subarraySum(int[] nums, int k) {        if (nums == null || nums.length == 0)            return 0;        Map
     
       map = new HashMap<>();        map.put(0, 1);        int sum = 0, cnt = 0;        for (int num : nums) {            sum += num;            cnt += map.getOrDefault(sum-k, 0);            map.put(sum, map.getOrDefault(sum, 0)+1);        }        return cnt;    }}
     

 第二种解法耗时更少