我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 560. 和為K的子數組

題目

給定一個整數數組和一個整數 k，你需要找到該數組中和為 k 的連續的子數組的個數。

示例 1 :

輸入:nums = [1,1,1], k = 2
輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況。

說明 :

• 數組的長度為 [1, 20,000]。
• 數組中元素的範圍是 [-1000, 1000] ，且整數 k 的範圍是 [-1e7, 1e7]。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

本題與LeetCode 1248. 統計「優美子數組」為同類問題，可對比學習；

思路1-用map記錄累加和；

思路解析：如果i和j之間的和為k，i之前的和為sum1，j之前的和為sum2，那麼就有sum2-sum1=k，所以使用map一次遍歷並記錄以sum為key，value為其出現的次數；
需要註意的是，起始map需要添加(0,1)對，代表sum-k為0時出現了1次，舉個例子，若k=10，數組第一項就是10，那麼sum-k=0，但0此時不在map，就少了一次count;

1. 建map，初始add(0,1)，新建統計變數count=0;
2. 遍歷累加sum，且看map中是否有sum-k，有則累加至count；
3. 以sum為key，更新map；

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $

演算法源碼示例

package leetcode;

import java.util.HashMap;

/**
 * @author ZhouJie
 * @date 2020年4月21日 下午8:47:12 
 * @Description: 560. 和為K的子數組
 *
 */
public class LeetCode_0560 {

}

class Solution_0560 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年4月21日 下午8:47:49 
	 * @param: @param nums
	 * @param: @param k
	 * @param: @return
	 * @return: int
	 * @Description: 1-map存儲首碼和；
	 *
	 */
	public int subarraySum_(int[] nums, int k) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		// 初始必須存入(0,1)，若不存而數組的第一項就是k，sum-k=0時就找不到0了
		map.put(0, 1);
		int sum = 0, count = 0;
		for (int val : nums) {
			sum += val;
			int key = sum - k;
			// 尋找之前是不是存過sum-k，有就表示找到了一個和為k的片段
			if (map.containsKey(key)) {
				count += map.get(key);
			}
			// 更新和為sum的出現次數
			map.put(sum, map.getOrDefault(sum, 0) + 1);
		}
		return count;
	}
}