560. 和为K的子数组（中等）_求和为k的子数组 dp-CSDN博客

本文链接：https://blog.csdn.net/di_ko/article/details/117898660

这篇博客介绍了如何利用前缀和和哈希表在O(N)的时间复杂度内解决寻找数组中和为k的连续子数组个数的问题。前缀和方法通过双重循环实现，时间复杂度为O(N^2)，而哈希表的引入将时间复杂度降低到O(N)，空间复杂度均为O(N)。文章详细解析了两种方法的思路及代码实现，并对比了它们的复杂度分析。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

思路：

1.前缀和

2.前缀和+哈希表

代码：

前缀和

class Solution {
    public int subarraySum(int[] nums, int k) {
		int n=nums.length;
		int sum=0;
		
		int[] dp=new int[n+1];
		dp[0]=0;
		
		//计算前缀和
		for(int i=1;i<=n;i++){
			//dp[i]代表不包括当前数nums[i]的前缀和
			dp[i]=dp[i-1]+nums[i-1];
		}
		
		for(int left=0;left<n;left++){
			for(int right=left;right<n;right++){
				if(dp[right+1]-dp[left]==k){
					sum++;
				}
			}
		}
		return sum;
    }
}

前缀和+哈希表：

class Solution {
    public int subarraySum(int[] nums, int k) {
		int n=nums.length;
		int preSum=0;
		int count=0;
		
		Map<Integer,Integer> map=new HashMap<>();
		//初始化：前缀和为0，有1个数字
		map.put(0,1);
		
		for(int num:nums){
			preSum+=num;
			if(map.containsKey(preSum-k)){
				//注意这里，并不是+1
                //利于了公式j-i==k的变化-->j-k==i
				count+=map.get(preSum-k);
			}
			map.put(preSum,map.getOrDefault(preSum,0)+1);
		}
		return count;
    }
}