时间轴

2026-03-11

init

题目：

P560 和为 K 的子数组

https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked

前缀和 - 前面的某个前缀和 = 这段区间的和

枚举：

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
#include <vector>
using std::vector;

class Solution {
    public:
        int subarraySum(vector<int> &nums, int k)
        {
                int i, j, n = nums.size();
                int cnt = 0;

                if (n == 0)
                        return 0;

                vector<int> prefix_sum(n + 1);

                // 计算前缀和
                prefix_sum[0] = 0;
                for (i = 1; i <= n; i++)
                        prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1];

                // prefix[j] - prefix[i] == nums.sum(i..j)
                for (i = 0; i <= n; i++) {
                        for (j = i + 1; j <= n; j++)
                                if (prefix_sum[j] - prefix_sum[i] == k)
                                        cnt++;
                }

                return cnt;
        }
};

哈希表：

只要之前出现过 umap[r+1] - k，就说明存在一个子数组和为 k。

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
#include <vector>
#include <unordered_map>

using std::unordered_map;
using std::vector;

class Solution {
    public:
        int subarraySum(vector<int> &nums, int k)
        {
                int res = 0;
                unordered_map<int, int> umap;
                vector<int> prefix_sum(nums.size() + 1, 0);

                umap[0] = 1;

                for (int i = 1; i < prefix_sum.size(); ++i) {
                        prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1];

                        // k=0 时, umap插入会把自身算进去
                        res += umap[prefix_sum[i] - k]; // 可能有多个,只能统计历史前缀和，不能把当前 preSum[i] 算进去。

                        umap[prefix_sum[i]] += 1;
                                                
                }

                return res;
        }
};