题目链接： 和为K的子数组

有关题目

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

题解

法一：枚举（超时）
代码一：

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int len = nums.size();int count = 0;for (int l = 0; l < len; l++){for (int r = l; r < len; r++){int sum = 0;for (int i = l; i <= r; i++){sum += nums[i];}if (sum == k)count++;}}return count;}
};

代码二①：

优化代码一：除去一些重复找的sum

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int count = 0;int len = nums.size();for (int l = 0; l < len; l++){int sum = 0;for (int r = l; r < len; r++){sum += nums[r];if (sum == k)count++;}}return count;}
};

代码二②：

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int count = 0;for (int start = 0; start < nums.size(); start){int sum = 0;for (int end = start; end >= 0; end--)sum += nums[end];if (sum == k)count++;}return count;}
};

法二：前缀和 + 哈希表

作用：构建前缀和数组，以快速计算区间和

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int count = 0;int len = nums.size();vector<int> sum(len + 1,0);//这边要注意，基础要扎实！！！for (int i = 1; i <= len; i++)sum[i] = sum[i - 1] + nums[i - 1];for (int l = 0; l < len; l++){for (int r = l; r < len; r++){if (sum[r + 1] - sum[l] == k)count++;}}return count;}
};

法三：前缀和 + 哈希表优化

思路：
前缀和pre[]表示的为前i项和
pre[i] = pre[j] + k;//移项
pre[i] - k = pre[j]//通过这个我们就可以找到是否存在连续的子数组哈希表优化
我们发现->前缀和pre[i]只跟上一次pre[i - 1]有关所以我们可以一个变量来降低维度

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int count = 0;//计数器int pre = 0;//前缀和unordered_map<int,int> mp;//键表示的为前缀和，值为和出现的次数mp[0] = 1;for (int num : nums){pre += num;//找到if (mp.find(pre - k) != mp.end())count += mp[pre - k];//没找到，添加次数++mp[pre];}return count;}
};