560. 和为 K 的子数组

题目描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

输入输出

1
2
3
4
5
输入：nums = [1,1,1], k = 2
输出：2

输入：nums = [1,2,3], k = 3
输出：2

基本思路

最佳的方法可以参照1. 两数之和 有相似之处 官方解答视频

设置一个pre[i]数组用来保存前缀和 num = [1,1,1], pre = [0,1,2,3]

哈希表用来保存<pre[i], 其出现的次数> 记录pre[i]出现的次数从左往右更新表答案

那么以i结尾的答案map[pre[i] - k]即可在O(1)内得到

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// 暴力 O(n^2)
class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        for(int left = 0; left < len; left++){
            int sum = 0;
            for(int right = left; right < len; right++){
                sum += nums[right];
                if(sum == k) count++;
            }
        }
        return count;
    }
}

// 前缀和 O(n^2)
class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for(int i = 0; i < len; i++){
            preSum[i + 1] = preSum[i] + nums[i]; 
        }

        for(int left = 0; left < len; left++){
            for(int right = left; right < len; right++){
                if(preSum[right + 1] - preSum[left] == k){
                    count++;
                }
            }
        }
        return count;
    }
}

// 前缀和+哈希表 时复O(n) 空复O(n)
class Solution {
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        Map<Integer, Integer> preSumMap = new HashMap<Integer, Integer>();
        preSumMap.put(0, 1);
        int preSum = 0;
        for(int num:nums) {
            preSum += num;
            if(preSumMap.containsKey(preSum - k)) {
                count += preSumMap.get(preSum - k);
            }
            preSumMap.put(preSum, preSumMap.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }
}