LeetCode 560. 和为K的子数组题解
Problem: 560. 和为 K 的子数组LeetCode 560. 和为K的子数组题解
https://img-blog.csdnimg.cn/img_convert/7616b18f29526b5f3a73c3fb5f8e7fd0.png
题目描述
给定一个整数数组 nums 和一个整数 k，要求返回数组中和为 k 的连续子数组的个数。子数组是数组中连续的非空元素序列。
示例
[*]输入：nums = , k = 2
[*]输出：2
这是一个经典的前缀和应用场景，同时通过不停优化，我们可以从O(N³)的暴力解法提拔到O(N)的哈希表解法。下面，我们分阶段具体讲解不同解法的逐步优化。
方法一：暴力解法
思路
[*]枚举所有可能的子数组出发点和终点，盘算每个子数组的和是否等于 k。
[*]三重循环：
[*]外层循环固定出发点 left。
[*]第二层循环选择不同的终点 right。
[*]内层循环盘算 范围内的和。
实现
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int len = nums.size();
int count = 0;
for (int left = 0; left < len; left++) {
for (int right = left; right < len; right++) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += nums;
}
if (sum == k) {
count++;
}
}
}
return count;
}
};
[*]时间复杂度：O(N³)
[*]空间复杂度：O(1)
方法二：暴力解法优化
思路
[*]进一步优化暴力解法，将最内层的求和操纵提前到第二层，避免重复求和。
[*]固定左边界，右边界扩展过程中累加盘算区间和，从而降低一个维度的循环。
实现
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
int len = nums.size();
for (int left = 0; left < len; left++) {
int sum = 0;
for (int right = left; right < len; right++) {
sum += nums;
if (sum == k) {
count++;
}
}
}
return count;
}
};
[*]时间复杂度：O(N²)
[*]空间复杂度：O(1)
方法三：前缀和
思路
[*]构建前缀和数组，用于快速盘算区间和，避免手动求和。
[*]前缀和数组界说为 preSum，表现 nums 到 nums 的和。
[*]通过公式 preSum - preSum == k 判断子数组和是否为 k。
实现
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int len = nums.size();
vector<int> preSum(len + 1, 0);
for (int i = 0; i < len; i++) {
preSum = preSum + nums;
}
int count = 0;
for (int left = 0; left < len; left++) {
for (int right = left; right < len; right++) {
if (preSum - preSum == k) {
count++;
}
}
}
return count;
}
};
[*]时间复杂度：O(N²)
[*]空间复杂度：O(N)
方法四：前缀和 + 哈希表优化
思路
[*]由于只关心区间和等于 k 的个数，可以使用哈希表记录前缀和的出现次数。
[*]假设当前前缀和为 preSum，那么我们必要查找是否有之前的前缀和满意 preSum - k。
[*]每当找到满意条件的 preSum - k，阐明存在一个区间和为 k 的子数组。
实现
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> prefixSumCount;
prefixSumCount = 1;
int preSum = 0;
int count = 0;
for (int num : nums) {
preSum += num;
if (prefixSumCount.find(preSum - k) != prefixSumCount.end()) {
count += prefixSumCount;
}
prefixSumCount++;
}
return count;
}
};
[*]时间复杂度：O(N)
[*]空间复杂度：O(N)
解题思路（详解）：前缀和 + 哈希表
1. 前缀和概念
前缀和是一种方便盘算数组区间和的方法，假设我们有一个数组 nums，prefixSum 表现从数组开始到 i 的元素之和，那么对于数组恣意区间 ，其和就可以表现为：
[ \text{sum}() = \text{prefixSum} - \text{prefixSum} ]
我们可以通过这个前缀和的头脑，判断从某个起始点 j 到 i 的子数组是否满意和为 k。
2. 使用哈希表存储前缀和出现的次数
我们用一个哈希表 prefixSumCount 来记录每个前缀和的出现次数，这样可以在常数时间内查找是否存在一个前缀和满意条件。
设当前的前缀和为 currentSum，则要找到的满意条件的前缀和 targetSum 应该是：
[ \text{targetSum} = \text{currentSum} - k ]
如果 targetSum 在哈希表中存在，阐明从这个 targetSum 之后到当前的 currentSum 之间的子数组和为 k，这样就可以统计符合条件的子数组。
3. 具体步调
[*]初始化：我们将 prefixSumCount = 1，因为如果一开始就满意 currentSum == k，那么这个子数组（重新开始的子数组）就符合条件。
[*]遍历数组：对于数组中的每个元素 num：
[*]盘算当前的前缀和 currentSum += num。
[*]查看哈希表中是否存在 currentSum - k，如果存在，阐明从这个 targetSum 之后的子数组和就是 k，因此加上 targetSum 出现的次数。
[*]将 currentSum 计入哈希表中，以便之后的元素可以用到这个前缀和。
4. 为什么这样可以盘算出所有满意条件的子数组？
假设 currentSum 代表了到达当前索引的前缀和，targetSum = currentSum - k 代表盼望找到的前缀和。每当我们发现这个 targetSum 出现过，意味着可以从这个 targetSum 位置开始，到当前的 currentSum 位置，这一段的和就为 k，因此我们加上符合条件的个数。
代码实现
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> prefixSumCount; // 哈希表，记录每个前缀和的出现次数
prefixSumCount = 1; // 初始化前缀和为0出现1次，便于从数组起始即满足条件的情况
int currentSum = 0; // 用于计算当前的前缀和
int count = 0; // 用于记录符合条件的子数组数量
// 遍历数组中的每一个元素
for (int num : nums) {
currentSum += num; // 计算当前前缀和
// 判断是否存在前缀和，使得 currentSum - k 出现过
// 若存在，说明从该前缀和之后到当前的 currentSum 之间的子数组和为 k
if (prefixSumCount.find(currentSum - k) != prefixSumCount.end()) {
count += prefixSumCount; // 加上满足条件的前缀和出现的次数
}
// 更新哈希表，记录当前前缀和的出现次数
prefixSumCount++;
}
return count; // 返回和为 k 的子数组数量
}
};
示例详解
示例 1
输入：nums = , k = 2
[*] 初始化：
[*]prefixSumCount = {0: 1}
[*]currentSum = 0
[*]count = 0
[*] 遍历数组：
[*] 第一个元素 1：
[*]currentSum = 0 + 1 = 1
[*]查找 currentSum - k = 1 - 2 = -1，不存在。
[*]更新 prefixSumCount：prefixSumCount = {0: 1, 1: 1}
[*] 第二个元素 1：
[*]currentSum = 1 + 1 = 2
[*]查找 currentSum - k = 2 - 2 = 0，存在，count += 1。
[*]更新 prefixSumCount：prefixSumCount = {0: 1, 1: 1, 2: 1}
[*] 第三个元素 1：
[*]currentSum = 2 + 1 = 3
[*]查找 currentSum - k = 3 - 2 = 1，存在，count += 1。
[*]更新 prefixSumCount：prefixSumCount = {0: 1, 1: 1, 2: 1, 3: 1}
[*] 效果：count = 2，以是返回 2。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]