我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 560. 和為K的子數組 題目 給定一個整數數組和一個整數 k ...
我的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;
- 建map,初始add(0,1),新建統計變數count=0;
- 遍歷累加sum,且看map中是否有sum-k,有則累加至count;
- 以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;
}
}