第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;
	}
}