第560题：和为K的子数组

解题思路

560. 和为K的子数组

这个题可以用暴力解法，也可以巧妙地用 前缀和+哈希表 来求解。

前缀和思想和滑动窗口会经常用在求子数组和子串问题上 ，求子数组通常需要用到前缀和+哈希表的配合使用。思路和1.两数之和基本相似，

代码

方法一：暴力破解

//运行时间：1239 ms   内存消耗：41.3MB
class Solution {
    /*
	 * 暴力破解：全遍历
	 */
	public static int subarraySum(int[] nums, int k) {
		int count = 0;
		for(int i=0 ; i<nums.length ; i++) {
			int sum=0;
			for(int j=i ; j<nums.length ; j++) {
				sum = sum + nums[j];
				if(sum == k) {
					count++;
				}
			}
			
		}
        return count;
    }
}
           

方法二：前缀和+哈希表

//运行时间：35 ms   内存消耗：40.9MB
class Solution {
    public static int subarraySum(int[] nums, int k) {
		Map<Integer , Integer> map = new HashMap<>();
		int count = 0;
		int presum = 0;//前缀和
//先加入0这个值，如果没有会出现这样的情况：eg:输入{1},k=1,presum - k = 0，但Map中没0这个值，所以会返回0，提前垫一个0进去，次数设置1，就会避免这种情况。
		map.put(0,1);   
		for (int i : nums) {
			presum = presum + i; //求每个位置的前缀和
			if(map.containsKey(presum - k)) {   //presume[i] - presume[j] = k
				count = count + map.get(presum - k);
			}
			//更新相同前缀和的次数
			map.put(presum,map.getOrDefault(presum, 0)+1);
		}
		return count;
	}
}