LeetCode 506.和为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
方法一 三重循环暴力
思路：
以0为子数组的开始下标，子数组的结束下标是0~len-1.里面再来一个循环来计算子数组的总和。
代码：
class Solution {
public int subarraySum(int[] nums, int k) {
int len=nums.length;
int count=0;
for(int left=0;left<len;left++){
for(int right = left;right<len;right++){
int sum=0;
for(int i=left;i<=right;i++){
sum+=nums[i];
}
if(sum==k) count++;
}
}
return count;
}
}方法二 暴力+一点点前缀和
思路：
我们其实只需要固定数组的开始下标，结束下标的指针一直移动，sum一直累加，累加到sum==k就代表找到一个，注意还可以继续往后走，因为数组可以有负数
代码：
class Solution {
public int subarraySum(int[] nums, int k) {
int len=nums.length;
int count=0;
for(int left=0;left<len;left++){
int sum=0;
//这里求sum就是用了上一次sum的结果（嗯...怎么不算前缀和呢）
for(int right = left;right<len;right++){
sum+=nums[right];
if(sum==k) count++;
}
}
return count;
}
}
方法三 前缀和+哈希表
思路：
这个思路好难，根本想不到。
前缀和是不带自己的的前面所有元素的和（震惊我了，我一直以为是带上当前元素）。
我们把所有前缀和算出来，按照次数put到哈希表中，之后我们看以i为结尾的子数组是否有和为k的，i的前缀和是preSum[i],如果有前缀和为k-preSum[i]的就是找到了。
代码更简洁但是更不好懂，不需要数组preSum[]去存前缀和，只需要从前往后走一遍就可以了。
代码：
class Solution {
public int subarraySum(int[] nums, int k) {
int len=nums.length;
int count=0;
//（前缀和，次数）
Map<Integer,Integer> map=new HashMap<Integer,Integer>();
map.put(0,1);
int preSum=0;
for(int i=0;i<len;i++){
preSum+=nums[i];
if(map.containsKey(preSum-k)){
count+=map.get(preSum-k);
}
map.put(preSum,map.getOrDefault(preSum,0)+1);
}
return count;
}
}参考链接：560. 和为 K 的子数组 - 力扣（LeetCode）
原文地址：https://blog.csdn.net/weixin_62438655/article/details/137909003
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！