560. 和为K的子数组

#560. 和为K的子数组

难度：中等
题目描述

解题思路

1、前缀和+哈希表 O(n)

public int subarraySum(int[] nums, int k) {        
	int sum = 0,re = 0;        
	HashMap<Integer,Integer> map=new HashMap<>();        
	map.put(0,1);  //初始化和为0 1次        
	for(int num:nums){            
		sum += num;            
		if(map.containsKey(sum-k)){  //如果存在子序和为sum-k                
			re += map.get(sum-k);            
		}            
		map.put(sum,map.getOrDefault(sum,0)+1);        
	}        
	return re;    
}

2、普通O(n2)解法

public int subarraySum(int[] nums, int k) {
   	int n =nums.length;
        int sum = 0,re = 0;
        for (int i = 0; i < n; i++) {
          	sum = 0;
    		for (int j = i; j < n; j++) {
     			sum += nums[j];
     			if(sum == k) {
      				re++;
     			}
    		}
   	}
        return re;
     }