题目描述
给定一个整数数组 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 结尾。