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 equal
        for (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 answer
            if (preSum.containsKey(sum_j)) {
                ans += preSum.get(sum_j);
            }
            preSum.put(sum_i, preSum.getOrDefault(sum_i, 0) + 1);
        }
        return ans;
    }
}