560. Subarray Sum Equals K

难度: Medium

题目描述

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

 

Constraints:

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

解题思路

代码实现

解决方案

java

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0; // 记录和为 k 的子数组数量
        int pre = 0; // 当前前缀和
        HashMap<Integer, Integer> map = new HashMap<>(); // 存储前缀和及其出现次数
        map.put(0, 1); // 初始化：前缀和为 0 出现了 1 次（对应空数组）

        for (int i = 0; i < nums.length; i++) {
            pre += nums[i]; // 更新当前前缀和

            // 如果存在前缀和为 pre - k，说明存在子数组和为 k
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }

            // 将当前前缀和加入 map，次数加 1
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }

        return count;
    }
}