560. 和为K的子数组

题目链接：

https://leetcode-cn.com/problems/subarray-sum-equals-k/

解题思路：

暴力

 1 class Solution {
 2     public int subarraySum(int[] nums, int k) {
 3         
 4         int i,j;
 5         int sum=0;
 6         int count=0;
 7         for(i=0;i<=nums.length-1;i++)
 8         {
 9             sum=0;
10             for(j=i;j<=nums.length-1;j++)
11             {
12                 sum=sum+nums[j];
13                 if(sum==k)
14                     count++;
15             }
16         }
17         return count; 
18     }
19 }

 1 class Solution {
 2     public int subarraySum(int[] nums, int k) {
 3         
 4         int []dp = new int[nums.length+1];
 5         
 6         for(int i=1;i<=nums.length;i++)
 7             dp[i] = dp[i-1]+nums[i-1];
 8         int res=0;
 9         HashMap<Integer,Integer> map = new HashMap<>();
10         for(int i=0;i<dp.length;i++)
11         {
12             if(map.containsKey(dp[i]-k))
13             {
14                 res+=map.get(dp[i]-k);
15             }
16             map.put(dp[i],map.getOrDefault(dp[i],0)+1);
17         }
18         return res;
19     }
20 }