560.和为k的子数组

题目描述

题解

暴力法

遍历数组, 将每个元素作为起点然后从该元素开始往后二次遍历

public int subarraySum(int[] nums, int k) {

    int count = 0;
    for (int left = 0; left < nums.length; left++) {
        int sum = 0;
        for (int right = left; right < nums.length; right++) {
            sum += nums[right];
            if (sum == k) {
                count++;
            }
        }
    }

    return count;
}

前缀树+哈希表

用一个哈希表记录当前的前缀和, 每遍历到一个元素都查看哈希表中是否含有presum - k的键, 如果有的话就说明满足条件.

public int subarraySum(int[] nums, int k) {

    int count = 0;
    int preSum = 0;
    HashMap<Integer, Integer> preSumFreq = new HashMap<>();
    preSumFreq.put(0, 1);

    for (int num : nums) {
        preSum += num;
        if (preSumFreq.containsKey(preSum - k)) {
            count += preSumFreq.get(preSum - k);
        }
        preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
    }

    return count;
}