文章目录
- 题目：560. 和为 K 的子数组
- 解题
- 方式一：暴力枚举
- 方式二：前缀和+Hash表
题目：560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
解题
方式一：暴力枚举
最简单的思路，两次循环，从当前i开始，逐个计算后面的和，在某一个和等于k时，结果个数+1。
/**
* 时间复杂度：O(n^2)
* 空间复杂度：O(1)
*/
class Solution {
public int subarraySum(int[] nums, int k) {
int len = nums.length;
int count = 0;
for (int i = 0; i < len; i++) {
int sum = 0;
// 寻找当前i及其后面的元素
for (int j = i; j < len; j++) {
sum = sum + nums[j];
if (sum == k) {
count++;
}
}
}
return count;
}
}方式二：前缀和+Hash表
基于方法一，利用【前缀和】数据结构优化，先得到一个与原数组对应的前缀和数组，（前缀和的概念：从0到当前位置i的所有数值累加），然后在前缀和的基础上，我们计算子数组的和就变为了 pre[i] - pre[j] = k，转变下，得到 pre[i] - k = pre[j] ,现在我们已知pre[i] 和 k，要求k的个数，不就是求pre[j]的个数！所以引入哈希表，记录前缀和出现的次数。
关于前缀和的内容，可看： 前缀和-数组中关于求和问题
/**
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
class Solution {
public int subarraySum(int[] nums, int k) {
// 从j到i的和为k(j < i)， 即sum[0~i] - sum[0~j] = k, 两个前缀和的差为k，
// 那sum[0~i] - k = sum[0~j]，求sum[0~j] 这个前缀和出现的次数
int len = nums.length;
// 前缀和数组
int[] preSumNums = new int[len + 1];
preSumNums[0] = 0;
for (int i = 0; i < len; i++) {
preSumNums[i + 1] = preSumNums[i] + nums[i];
}
// map: key为前缀和 value为出现的次数
HashMap<Integer, Integer> map = new HashMap<>();
int count = 0;
for (int i = 0; i < preSumNums.length; i++) {
if (map.containsKey(preSumNums[i] - k)) {
count += map.get(preSumNums[i] - k);
}
map.put(preSumNums[i], map.getOrDefault(preSumNums[i], 0) + 1);
}
return count;
}
}
代码优化下：
class Solution {
public int subarraySum(int[] nums, int k) {
// i - j = k; k已知，i就是前缀和，求j前缀和出现的次数
int len = nums.length;
// 用一个变量记录当前的前缀和
int preNum = 0;
int count = 0;
// key 前缀和,value 次数
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0,1);
for (int i = 0; i < len; i++) {
preNum += nums[i];
if (map.containsKey(preNum - k)) {
count += map.get(preNum - k);
}
map.put(preNum, map.getOrDefault(preNum, 0) + 1);
}
return count;
}
}