知名做网站公司有哪些google搜索首页
【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;}
};
LeetCode链接：560.和为k的子数组