简单 网站设计珠海cp网站建设

题目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;}
};

LeetCode链接：560.和为k的子数组