📝 题目描述

题目链接：和为 K 的子数组

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

子数组是数组中元素的连续非空序列。

示例：

1
2
3
4
5
6
7
8
9
10
11

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

💡 解题思路

方法一：暴力解法

最容易想到的朴素解法，使用一个二重循环，列举出所有可能的开头i和结尾j，然后计算它们代表的子数组的和，在计算和时，由于我们的内层循环（代表结尾的j）是逐个往后列举的，因此可以令sum += nums[j]而不必重新遍历来计算和，稍微降低了一下复杂度。

方法二：前缀和 + 哈希表优化

方法一中，对于每个开头i，我们要遍历i后的每一个元素来找结尾j。

对于这种：知道最终和k，知道其中一个元素i，求另一个元素j的问题，有点类似两数之和，我们可以使用相似的思路来解决。

我们可以维护一个数组pre[i]，它代表从nums[0]到nums[i]的和，也就是：

pre[i]=nums[0]+nums[1]+nums[2]+...+nums[i]pre[i] = nums[0] + nums[1] + nums[2] + ... + nums[i]

然后我们调转一下开头结尾的代号，我们让i表示结尾，j表示开头。

这样一来，子数组 nums[j...i] 的和可以表示为 pre[i] - pre[j-1]。

比如j = 3, i = 5，求子数组 nums[j...i] 的和，也就是 nums[3...5] 的和，就需要表示为 pre[i] - pre[j-1]，即 pre[5] - pre[2]。

pre[5]=nums[0]+nums[1]+nums[2]+nums[3]+nums[4]+nums[5]pre[2]=nums[0]+nums[1]+nums[2]pre[5] = nums[0] + nums[1] + nums[2] + nums[3] + nums[4] + nums[5] \\ pre[2] = nums[0] + nums[1] + nums[2]

同时，我们计算 pre[i] 时，其可以由 pre[i−1] 递推而来，即：

pre[i]=pre[i−1]+nums[i]pre[i]=pre[i−1]+nums[i]

那么 “[j..i] 这个子数组和为 k” 这个条件我们可以转化为：

pre[i]−pre[j−1]=kpre[i]−pre[j−1]=k

简单移项可得符合条件的下标 j 需要满足：

pre[j−1]=pre[i]−kpre[j−1]=pre[i]−k

也就是说，当我们遍历到位置 i 时，我们只需要问：“在我之前，有多少个位置的前缀和等于 pre[i] - k？

所以，我们考虑以 i 结尾的和为 k 的连续子数组个数时，只要统计有多少个和为 pre[i]−k 的位置即可。我们建立哈希表 mp，以和为键，以和的出现次数为值，记录每个和出现的次数，从左往右，一边更新 mp 一边统计答案，那么以 i 结尾的答案 mp[pre[i]−k] 即可在 O(1)O(1) 时间内得到。最后的答案即为所有下标结尾的和为 k 的子数组个数之和。

需要注意的是，从左往右边更新边计算的时候已经保证了 mp[pre[i]−k] 里记录的 pre[j] 的下标范围是 0≤j≤i0≤j≤i 。同时，由于 pre[i] 的计算只与前一项的答案有关，因此我们可以不用建立 pre 数组，直接用 pre 变量来记录 pre[i−1] 的结果即可。

🔧 代码实现

1、暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0, sum = 0;
        for(int i = 0; i < n; i++){
            sum = 0;
            for(int j = i; j < n; j++){
                sum += nums[j];
                if (sum == k){
                    ans++;
                }
            }
        }
        return ans;
    }
};

2、前缀和 + 哈希表优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0, pre = 0;
        // 其中 key 是前缀和，value 是该前缀和出现的次数
        unordered_map<int, int> mp;
        // 初始化：前缀和为 0 出现了一次（相当于空数组的情况）
        // 如果 nums[0...i] 本身和就为 k，那么 pre[i] - k = 0，需要统计这种情况
        mp[0] = 1;
        for(int i = 0; i < n; i++){
            // 计算当前前缀和
            pre += nums[i];
            // 查找是否存在一个历史前缀和 target，使得 pre - target = k
            // 即 target = pre - k
            if (mp.find(pre - k) != mp.end()){
                ans += mp[pre - k];
            }
            // 将当前前缀和记录到 mp 中
            mp[pre]++;
        }
        return ans;
    }
};

📊 复杂度分析

1、暴力解法

  • 时间复杂度：O(N2)O(N^2)。使用了双重遍历。
  • 空间复杂度：O(1)O(1)。没有额外使用随输入规模增大的空间。

2、前缀和 + 哈希表优化

  • 时间复杂度：O(N)O(N)，其中 NN 为数组的长度。遍历数组的时间复杂度为 O(N)O(N)，中间利用哈希表查询删除的复杂度均为 O(1)O(1)，因此总时间复杂度为 O(N)O(N)。
  • 空间复杂度：O(N)O(N)，其中 NN 为数组的长度。哈希表在最坏情况下可能有 N 个不同的键值，因此需要 O(N)O(N) 的空间复杂度。

🎯 总结

  • 核心思想：如何从朴素解法想到使用前缀和 + 哈希表优化。