1、题目：LCR 010. 和为 K 的子数组

• https://leetcode.cn/problems/QTMn0o/description/

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。示例 1：
输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况示例 2：
输入:nums = [1,2,3], k = 3
输出: 2

审题：

• 输入一个整数数组和一个整数值k，要求从整数数组中找出存在的子数组个数，要求子数组的和等于k

2、暴力解法

• 双层for循环，外层for循环定位子数组的开始位置，内层for循环定义子数组的结束位置，
• 在内层for循环中，将子数组所有的元素相加，判断结果累加结果sum是否等于目标值k，如果等于则找到符合要求的子数组，符合子数组个数结果值+1

代码实现

int subarraySum(vector<int> &nums, int k)
{int res = 0;int size = nums.size();int sum = 0;for (int i = 0; i < size; i++){sum = 0;for (int j = i; j < size; j++){sum += nums[j];if (k == sum){res++;}}}return res;
}

3、数组累加法

• 将数组中所有元素的值累加起来，使用哈希表保存子数组累加和出现的次数，判断子数组的累加和是否等于目标值k
• 中间子数组的累加和，可以通过整个范围的子数组累加和，减去前面部分子数组的累加和。
• 例子：

有数组 {1，2，3，4，5，6} 加入要求子数组和为9的子数组出现的个数
可以通过累加计算得到前三个数组元素的累加和 S3 = 1+2+3 = 6
前5个数组元素累加和为 S5 = 1+2+3+4+5 = 15；
那子数组累加和为9的子数组 = S5 - S3；
可通过计算累加相减是否等于目标值来求符合条件的子数组

代码实现

int subarraySum(vector<int> &nums, int k)
{int res = 0;std::map<int, int> sumCountMap;// 往map中插入元素sumCountMap[0] = 1;int sum = 0;for (int i = 0; i < nums.size(); i++){sum += nums[i];// 判断是否存在 sum-k的key值if (sumCountMap.find(sum - k) != sumCountMap.end()){res += sumCountMap.at(sum - k);}// 在往map中插入累加值int count = 0;if (sumCountMap.find(sum) != sumCountMap.end()){count = sumCountMap.at(sum);}sumCountMap[sum] = count + 1;}return res;
}

4、总结

• 求子数组的累加和等于某个目标值，如果数组元素全是正整数，可以使用双指针解法，但数组元素只是整数，那就会存在正整数与负整数，使用双指针累加法就覆盖不到所有结果。
• 暴力解法使用双层for循环，可以检索所有的子数组情况，但时间复杂度为n的平方
• 采用数组累加求和方式，可通过子数组累加和相减得到某段区域的子数组累加和。使用哈希表保存子数组累加和出现的次数
• map数据结构使用，使用find方法查询key值是否存在，at方法获取value值，还可以使用赋值语句[]获取value值