image.png

解法

暴力解法，双重遍历。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            // j从i开始，进行计算
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

前缀和解法，对于连续类树和数组都很好用

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        // 记录前缀和出现的次数，key为前缀和的值，value为出现次数
        Map<Integer, Integer> countMap = new HashMap();
        // 0出现的次数为1，用于作为基准计算
        countMap.put(0, 1);
        int pre = 0;
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            // pre-k出现的次数，即为满足条件的连续子数组数
            if (countMap.containsKey(pre - k)) {
                count += countMap.get(pre - k);
            }
            countMap.put(pre, countMap.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}