题目描述

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

示例 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

解题思路

这道题要求找出和为k的连续子数组的个数。我们可以有多种思路：

1. 暴力解法

最直观的方法是枚举所有可能的子数组，计算它们的和，并统计和为k的子数组个数。但这种方法的时间复杂度是O(n²)，对于较大规模的数组会超时。

2. 前缀和 + 哈希表

更高效的解法是使用前缀和和哈希表的组合：

• 使用一个变量 sum 记录从数组起始位置到当前位置的所有元素之和
• 使用哈希表 prefixSum 记录每种前缀和出现的次数
• 对于每个位置，我们检查 sum - k 是否在哈希表中存在
  • 如果存在，说明从某个位置到当前位置的子数组和为k
  • 将哈希表中 sum - k 对应的次数加到结果中

这种方法的时间复杂度为O(n)，空间复杂度为O(n)。

代码实现

class Solution {public int subarraySum(int[] nums, int k) {int count = 0;int sum = 0;// 哈希表：前缀和 -> 出现次数HashMap<Integer, Integer> prefixSum = new HashMap<>();// 初始化：前缀和为0的情况出现了1次prefixSum.put(0, 1);for (int num : nums) {// 累加前缀和sum += num;// 如果 (sum - k) 存在于哈希表中，说明存在若干个前缀和为 (sum - k) 的子数组// 这些子数组与当前位置之间的子数组的和为kif (prefixSum.containsKey(sum - k)) {count += prefixSum.get(sum - k);}// 将当前前缀和加入哈希表，或更新其出现次数prefixSum.put(sum, prefixSum.getOrDefault(sum, 0) + 1);}return count;}
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历一次数组。
• 空间复杂度：O(n)，最坏情况下哈希表需要存储 n 个不同的前缀和。

解题思路详解

这道题的关键在于理解前缀和与哈希表的结合使用。前缀和是指从数组起始位置到当前位置的元素和。

如果我们有两个位置 i 和 j，且它们的前缀和之差等于 k，即 prefixSum[j] - prefixSum[i] = k，那么从位置 i+1 到位置 j 的子数组和就是 k。

转化一下等式：prefixSum[j] - k = prefixSum[i]，所以我们只需要知道在位置 j 之前有多少个位置 i 满足 prefixSum[i] = prefixSum[j] - k。

使用哈希表记录每个前缀和出现的次数，当我们遍历到位置 j 时，就可以直接查询有多少个位置 i 满足条件，从而在O(1)时间内知道有多少个和为k的子数组以位置 j 结尾。