10 和为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

思路1

滑动窗口

1、检查参数的合法性

2、循环数组nums，从0到nums.size()-1，记下标为i，定义满足次数的变量_count=0。

3、循环下标i到0的累加和，nums[i]+nums[i-1]、nums[i]+nums[i-1]+nums[i-2]....... nums[i+nums[i-1]+nums[i-2]+nums[0]。判断累加和是否有满足和等于k的。

4、满足条件k+1,不满足条件忽略，最后返回_count。

class Solution { public: int subarraySum(vector<int>& nums, int k) { if(nums.empty()) return 0; int _count=0; for(int i=0;i<nums.size();i++){ int _sum=0; for(int j=i;j>=0;j--){ _sum+=nums[j]; if(_sum==k) _count++; } } return _count; } }; //写法2 class Solution { public: int subarraySum(vector<int>& nums, int k) { int n=nums.size(); if(n==0) return 0; int _ans=0; for(int i=0;i<n;i++){ int _sum=0; for(int j=i;j<n;j++){ _sum+=nums[j]; if(_sum==k) _ans++; } } return _ans; } };

思路2

官方解法我们定义 pre[i] 为 [0..i] 里所有数的和，则 pre[i] 可以由 pre[i−1] 递推而来，即：

pre[i]=pre[i−1]+nums[i] 那么「[j..i] 这个子数组和为 k 这个条件我们可以转化为

pre[i]−pre[j−1]==k 简单移项可得符合条件的下标 j 需要满足

pre[j−1]==pre[i]−k

步骤

1、检查参数的合法性，定义一个hash表，key是pre[i]，value是出现的次数。

2、循环数组nums，计算每一个的pre[i],然后查找hash表中是否存在k-pre[i]这个值，

3、若存在，则count++，若不存在则跳过。

4、把pre[i]插入hash表中。

5、循环结束，返回count。

class Solution { public: int subarraySum(vector<int>& nums, int k) { if(nums.empty()) return 0; unordered_map<int,int> hash; int _count=0; int _sum=0; hash[0]=1; for(int i=0;i<nums.size();i++) { _sum+=nums[i]; unordered_map<int,int>::iterator it=hash.find(_sum-k); if(it==hash.end()){ hash[_sum]++; continue; } _count+=hash[_sum-k]; hash[_sum]++; } return _count; } };

推荐一个零声教育学习教程，个人觉得老师讲得不错，分享给大家：[Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，点击立即学习:链接