【問題描述】[第560題][和為K的子數組][中等]

給定一個整數數組和一個整數 k，你需要找到該數組中和為 k 的連續的子數組的個數。示例 1 :輸入:nums = [1,1,1], k = 2 輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況。 說明 :數組的長度為 [1, 20,000]。 數組中元素的范圍是 [-1000, 1000] ，且整數 k 的范圍是 [-1e7, 1e7]。

【解答思路】

1. 暴力

時間復雜度：O(N^2) 空間復雜度：O(1)

public int subarraySum(int[] nums, int k) {int count = 0;int len = nums.length;for (int left = 0; left < len; left++) {int sum = 0;// 區間里可能會有一些互相抵銷的元素for (int right = left; right < len; right++) {sum += nums[right];if (sum == k) {count++;}}}return count;}

2.前綴和

• 構建前綴和數組，以快速計算區間和；
• 注意在計算區間和的時候，下標有偏移。
  時間復雜度：O(N^2) 空間復雜度：O(N)

public class Solution {public int subarraySum(int[] nums, int k) {int len = nums.length;// 計算前綴和數組int[] preSum = new int[len + 1];preSum[0] = 0;for (int i = 0; i < len; i++) {preSum[i + 1] = preSum[i] + nums[i];}int count = 0;for (int left = 0; left < len; left++) {for (int right = left; right < len; right++) {// 區間和 [left..right]，注意下標偏移if (preSum[right + 1] - preSum[left] == k) {count++;}}}return count;} }

3. 前綴和 + 哈希表優化

時間復雜度：O(N) 空間復雜度：O(1)
由于只關心次數，不關心具體的解，我們可以使用哈希表加速運算；
由于保存了之前相同前綴和的個數，計算區間總數的時候不是一個一個地加，時間復雜度降到了 O(N)O(N)。

preSumFreq.put(0, 1)：數組中有些數直接就等于k

import java.util.HashMap; import java.util.Map;public class Solution {public int subarraySum(int[] nums, int k) {// key：前綴和，value：key 對應的前綴和的個數Map<Integer, Integer> preSumFreq = new HashMap<>();// 對于下標為 0 的元素，前綴和為 0，個數為 1preSumFreq.put(0, 1);int preSum = 0;int count = 0;for (int num : nums) {preSum += num;// 先獲得前綴和為 preSum - k 的個數，加到計數變量里if (preSumFreq.containsKey(preSum - k)) {count += preSumFreq.get(preSum - k);}// 然后維護 preSumFreq 的定義preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1); //getOrDefault 有就是get preSum的對應的值 不存在就為0}return count;} } public class Solution {public int subarraySum(int[] nums, int k) {// 記錄區間和為 k 的個數和數組前綴元素和。int ans = 0, curr = 0;// 創建 hashMap 記錄數組前綴和以及當前和對應的前綴個數。HashMap<Integer, Integer> map = new HashMap<>();// 遍歷前初始化前綴和為 0 的個數為 1 。map.put(0, 1);for (int num : nums) {// 依次遍歷并累加數組元素。curr += num;int pre = curr - k;// 如果之前有前綴和等于 curr - k ，表示從該前綴之后到當前元素區間和為 k 。if (map.containsKey(pre)) {// 疊加和為 k 的區間個數。ans += map.get(pre);}// 遍歷完每個元素后，記錄當前前綴和以及個數。if (map.containsKey(curr)) {map.put(curr, map.get(curr) + 1);} else {map.put(curr, 1);}}return ans;} }

【總結】

1. 暴力優化

2.哈希表 關于次數的優化

3.HashMap

（1） 插入鍵值對數據
public V put(K key, V value)
（2）根據鍵值獲取鍵值對值數據
public V get(Object key)
（3）獲取Map中鍵值對的個數
public int size()
（4）判斷Map集合中是否包含鍵為key的鍵值對
public boolean containsKey(Object key)
（5）判斷Map集合中是否包含值為value的鍵值對
boolean containsValue(Object value)
（6）判斷Map集合中是否沒有任何鍵值對
public boolean isEmpty()
（7）清空Map集合中所有的鍵值對
public void clear()
（8）根據鍵值刪除Map中鍵值對
public V remove(Object key)

遍歷hashMap

for (Integer key : map.keySet()) { if (map.get(key) == 1) {return key;}

原文鏈接：https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/bao-li-jie-fa-qian-zhui-he-qian-zhui-he-you-hua-ja/
參考鏈接：https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/560ti-he-wei-kde-zi-shu-zu-by-iceblood/

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第560题][和为K的子数组][Hashmap][数组]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。