560. Subarray Sum Equals K

Prefix Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] prefixSums = new int[nums.length + 1];
        for (int i = 1; i < prefixSums.length; i++) {
            prefixSums[i] = prefixSums[i - 1] + nums[i - 1];
        }

        int count = 0;
        Map<Integer, Integer> prefixSumToCountMap = new HashMap<>();
        prefixSumToCountMap.put(0, 1); // 不要忘记前缀和为 0 的情况
        for (int i = 1; i < prefixSums.length; i++) {
            count += prefixSumToCountMap.getOrDefault(prefixSums[i] - k, 0); // 注意此处是 prefixSums[i] - k
            prefixSumToCountMap.put(prefixSums[i], prefixSumToCountMap.getOrDefault(prefixSums[i], 0) + 1);
        }

        return count;
    }
}

Prefix Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;

        Map<Integer, Integer> prefixSumToCountMap = new HashMap<>();
        prefixSumToCountMap.put(0, 1);

        int prefixSum = 0;
        for (int num : nums) {
            prefixSum += num;

            count += prefixSumToCountMap.getOrDefault(prefixSum - k, 0); // 注意 key 是前缀和，所以此处是 prefixSum - k
            prefixSumToCountMap.put(prefixSum, prefixSumToCountMap.getOrDefault(prefixSum, 0) + 1);
        }

        return count;
    }
}

注意题目输入数据中可能存在负数，可能存在重复的前缀和，所以我们引入了 HashMap 用于存储重复的前缀和个数。

References

560. Subarray Sum Equals K
剑指 Offer II 010. 和为 k 的子数组