【LeetCode刷题】前缀和解决问题：560.和为k的子数组

本文主要是介绍【LeetCode刷题】前缀和解决问题：560.和为k的子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【LeetCode刷题】Day 16

题目1：560.和为k的子数组
- 思路分析：
- 思路1：前缀和 + 哈希表

在这里插入图片描述

题目1：560.和为k的子数组

在这里插入图片描述

思路分析：

问题1：怎样找到数组所有子数组？

方式一：暴力枚举出来，以i开始，列出以i开头的所有子数组[i,j]（i <= j<= size-1）再i++，列出下一个位置开头的所有子数组。

方式二：前缀和思想，我们用dp[i]来表示[0,i]的数组，要找以i结尾的所有子数组，只需要 dp[i]-dp[j]（0<= j <= i-1）就可以表示所有以i结尾的子数组

下图就这题引入：
请添加图片描述

在这里插入图片描述
问题2：为什么这样转换？

因为在求以i结尾的所有子数组的和时，i和k是不变的，他们的差值也是固定值，所以问题就转换为：前缀和为k的数量，注意: 0<= j <=i-1

问题3：怎样不创建前缀和数组，但统计数量？

用一个int sum来就可以实现，再加上哈希表，就能解决这些问题。

思路1：前缀和 + 哈希表

代码实现：

class Solution {
public:int subarraySum(vector<int>& nums, int k) {//前缀和+哈希表unordered_map<int,int> hash;int sum=0 , ret=0;//处理当sum[i]本身等于k的情况hash[0] = 1;for(auto i : nums){sum+=i;//判断是否存在值为sum-k的key，有就加数量if(hash.count(sum - k)) ret+=hash[sum-k];hash[sum]++;}return ret;}
};