Problem: 560. 和為 K 的子數組

題目描述

思路

1.初始化一個哈希表preSum，用于記錄前綴和及其出現次數,ans記錄和為k的子數組數量、sum_i記錄當前前綴和；
2.將前綴和為 0 的情況存入哈希表，表示前綴和為 0 出現了一次。;
3.對數組 nums 進行遍歷，計算當前的前綴和 sum_i。計算當前前綴和減去 k 的值 sum_j，以此檢查是否存在從某個位置到當前位置的子數組和為 k。
4.如果 sum_j 存在于哈希表中，說明存在某個位置到當前位置的子數組和為 k，將其出現的次數累加到 ans 中。將當前前綴和 sum_i 存入哈希表，并記錄其出現次數。

復雜度

時間復雜度:

$O(n)$;其中$n$為數組的長度

空間復雜度:

$O(n)$

Code

class Solution {/*** Subarray Sum Equals K** @param nums Given array* @param k    Given number* @return int*/public int subarraySum(int[] nums, int k) {int n = nums.length;// Use HashMap to record the prefix and its occurrence//map< prefix sum, number of occurrences of the prefix sum >Map<Integer, Integer> preSum = new HashMap<>();preSum.put(0, 1);int ans = 0, sum_i = 0;// sum[j] and sum[i] -k are equalfor (int i = 0; i < n; i++) {sum_i += nums[i];// prefix and nums[0....j]int sum_j = sum_i - k;// If sum_j exists, update the answerif (preSum.containsKey(sum_j)) {ans += preSum.get(sum_j);}preSum.put(sum_i, preSum.getOrDefault(sum_i, 0) + 1);}return ans;}
}