算法力扣560题和为-K-的连续子数组之深入思考
【算法】力扣560题：和为 K 的连续子数组之深入思考
前言
该题是面试手撕的高频题，如果能这种类型题的多个思路融会贯通，那相信你也能“打十个”！
本题与 相同
顺带一提：下面题解提供了cpp的版本，如果需要其他语言版本可以找ai工具转换一下即可。重要的是解题思路，语言实现是次要的
题目：和为 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
参考思路
首先明确什么是子数组，什么是子序列
子数组（Subarray）
定义：子数组是原数组中连续的一段元素。
特点：
- 元素必须是连续的。
- 顺序必须与原数组一致。
示例：
- 原数组：[1, 2, 3, 4]
- 子数组：[1, 2]、[2, 3, 4]、[3]
- 非子数组：[1, 3]（不连续）、[2, 1]（顺序不一致）
子序列（Subsequence）
定义：子序列是从原数组中选取一些元素，这些元素不一定连续，但顺序必须与原数组一致。
特点：
- 元素可以不连续。
- 顺序必须与原数组一致。
示例：
- 原数组：[1, 2, 3, 4]
- 子序列：[1, 3]、[2, 4]、[1, 2, 4]
- 非子序列：[2, 1]（顺序不一致）
这道题是求子数组，也就是元素必须连续，同时注意到元素有正有负
方法一：暴力遍历
这题第一反应，可以用暴力法，遍历左右的边界去求解每个子数组的和是否满足条件
时间复杂度：
时间复杂度是 O(n^2)，因为它们都需要两层循环来枚举所有子数组。
空间复杂度：
方法的空间复杂度都是 O(1)，只使用了常数级别的额外空间。
然而暴力方法可能会导致超时，那么有没有更优的方法呢？
方法二：前缀和 + 哈希表
那么就需要知道“前缀和”这个概念了，如果有不懂的可以上网搜索一下相关概念
这里简单讲述一下
前缀和 prefixSum[i] 表示从数组开头到第 i 个元素的累加和。
例如，数组 nums = [1, 2, 3] 的前缀和为：
prefixSum[0] = 1
prefixSum[1] = 1 + 2 = 3
prefixSum[2] = 1 + 2 + 3 = 6假设我们有两个前缀和 prefixSum[i] 和 prefixSum[j]，其中 i < j。
那么子数组 nums[i+1…j] 的和可以表示为：
sum(nums[i+1..j]) = prefixSum[j] - prefixSum[i]如果 prefixSum[j] - prefixSum[i] == k，则说明子数组 nums[i+1…j] 的和为 k
那么回到本题：
我们希望找到子数组的和等于 k，即：
sum(nums[i+1..j]) = k也就是 j 下标的前缀和 减去 i 下标的前缀和
prefixSum[j] - prefixSum[i] = k将等式变形：
prefixSum[i] = prefixSum[j] - k我们维护一个哈希表 prefixSumCount，用于记录每个前缀和出现的次数。
当我们计算当前前缀和 sum 时，可以通过查找 sum - k 是否在哈希表中，来判断是否存在若干个子数组的和为 k。
如果 sum - k 存在于哈希表中，说明在之前的某个位置 i，前缀和 prefixSum[i] = sum - k。
根据等式 prefixSum[i] = prefixSum[j] - k，这意味着从位置 i+1 到当前位置 j 的子数组和为 k。
简而言之，就是想找到一个之前出现过的 prefixSum[i] 满足 prefixSum[j] - k，那么这个nums[i+1…j] 就是符合题意的答案，而这个判断这个 prefixSum[i]（某个下标的前缀和）是否之前出现过则可以用哈希表来维护
示例解析：
假设 nums = [1, 2, 3]，k = 3：
初始化：
prefixSumCount = {0: 1}（表示前缀和为 0 出现了 1 次）。
遍历过程：
第 0 个元素（num = 1）：
当前前缀和：sum = 1
检查 sum - k = 1 - 3 = -2 是否在哈希表中：不存在。
更新哈希表：prefixSumCount = {0: 1, 1: 1}
第 1 个元素（num = 2）：
当前前缀和：sum = 1 + 2 = 3
检查 sum - k = 3 - 3 = 0 是否在哈希表中：存在，prefixSumCount[0] = 1。
这意味着存在一个前缀和为 0，即从数组开头到当前位置的子数组和为 3（子数组 [1, 2]）。
更新计数器：count += 1。
更新哈希表：prefixSumCount = {0: 1, 1: 1, 3: 1}
第 2 个元素（num = 3）：
当前前缀和：sum = 1 + 2 + 3 = 6
检查 sum - k = 6 - 3 = 3 是否在哈希表中：存在，prefixSumCount[3] = 1。
这意味着存在一个前缀和为 3，即从某个位置到当前位置的子数组和为 3（子数组 [3]）。
更新计数器：count += 1
更新哈希表：prefixSumCount = {0: 1, 1: 1, 3: 1, 6: 1}
最终结果：
count = 2
时间复杂度：O(n)。
只需要遍历数组一次，每次操作（计算前缀和、查找哈希表、更新哈希表）都是 O(1)。
空间复杂度：O(n)。
哈希表最多存储 n 个前缀和。
参考题解
方法一：暴力遍历
第一种方法：暴力解法
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int result = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = i; j < n; ++j) {
sum += nums[j];
if (sum == k) {
++result;
}
}
}
return result;
}
};方法二：前缀和 + 哈希表
第二种方法：前缀和 + 哈希表
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int result = 0;
int n = nums.size();
unordered_map<int ,int> map;
map.insert({0, 1});
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += nums[i];
if (map.find(sum - k) != map.end()) {
result += map.at(sum - k);
}
map[sum]++;
}
return result;
}
};深入思考
滑动数组？
好！到这里可能有人会有疑惑，能不能用滑动数组的方式来解呢？
需要注意的是这个题目的数组里面包含负数！！
这是因为滑动窗口的核心思想是通过调整窗口的左右边界来动态维护一个满足条件的子数组，而这种调整依赖于数组元素的单调性。如果数组中包含负数，滑动窗口的单调性会被破坏，导致无法正确调整窗口边界。
非负数组的单调性
在非负数组中，子数组和随着窗口的扩展（右边界右移）是单调不减的。
当子数组和超过目标值时，可以通过收缩窗口（左边界右移）来减少子数组和，使其重新满足条件。
包含负数的数组破坏了单调性
如果数组中包含负数，子数组和随着窗口的扩展不一定增加，可能会减少。
当子数组和超过目标值时，收缩窗口（左边界右移）可能会导致子数组和进一步增加，而不是减少。
这种情况下，滑动窗口无法正确调整窗口边界，从而无法找到所有满足条件的子数组。
所以使用滑动窗口一定要注意下面几点：
无法处理负数：
负数的存在会破坏子数组和的单调性，导致滑动窗口无法正确调整边界。
无法处理零：
如果数组中有零，滑动窗口可能会重复计数某些子数组。
无法处理目标值为负数：
如果目标值 k 是负数，滑动窗口的逻辑会失效，因为子数组和可能会在扩展窗口时减少。
好的，如果假设题目给的是非负数组，这里也给出参考题解
如果数组中的元素都是非负数，可以使用滑动窗口来优化时间复杂度。
维护一个窗口 [left, right]，通过调整窗口的大小来寻找和为 k 的子数组。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
int sum = 0;
int left = 0;
for (int right = 0; right < nums.size(); ++right) {
sum += nums[right];
while (sum > k && left <= right) {
sum -= nums[left];
left++;
}
if (sum == k) {
count++;
}
}
return count;
}
};复杂度分析：
- 时间复杂度：O(n)，每个元素最多被访问两次（一次加入窗口，一次移出窗口）。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
动态规划？
好！到这里可能有人会有疑惑，能不能用动态规划的方式来解呢？
这题可以用动态规划（DP）来做，但动态规划并不是最优的解法，因为它的时间复杂度仍然是 O(n^2)，和暴力解法相同。
定义状态：
设 dp[i][j] 表示子数组 nums[i…j] 的和。
我们的目标是找到所有满足 dp[i][j] == k 的子数组。
状态转移方程：
对于每个子数组 nums[i…j]，其和可以通过以下方式计算：
dp[i][j] = dp[i][j-1] + nums[j]其中：
- dp[i][j-1] 是子数组 nums[i…j-1] 的和。
- nums[j] 是当前元素。
初始化：
对于每个 i，dp[i][i] = nums[i]（即单个元素的子数组和）。
遍历顺序：
外层循环枚举子数组的起始位置 i。
内层循环枚举子数组的结束位置 j（从 i 到 n-1）。
统计结果：
在计算 dp[i][j] 的过程中，如果 dp[i][j] == k，则增加计数器 count。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
int count = 0;
// 定义 DP 数组
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
dp[i][i] = nums[i]; // 初始化单个元素的子数组和
if (dp[i][i] == k) {
count++;
}
for (int j = i + 1; j < n; ++j) {
dp[i][j] = dp[i][j - 1] + nums[j]; // 状态转移
if (dp[i][j] == k) {
count++;
}
}
}
return count;
}
};复杂度分析
时间复杂度：
外层循环遍历 n 次，内层循环最多遍历 n 次，因此总时间复杂度为 O(n^2)。
空间复杂度：
需要一个 n x n 的二维数组 dp，因此空间复杂度为 O(n^2)。
**所以说动态规划方法去解这个题和暴力法差不多，并不是最优解
并且注意的是如果数组很大，仅在栈上分配内存很可能导致超出内存限制，导致无法100%AC这道题**
这里可能会想那什么题适合用动态规划去做呢？
动态规划通常适用于以下类型的问题：
- 最优子结构：问题的最优解可以通过子问题的最优解推导出来。
- 重叠子问题：在求解过程中，子问题会被重复计算。
- 状态转移方程：可以通过某种规律从子问题的解推导出当前问题的解。
比如下面几种问题可以用动态规划来做
最大/最小子数组和问题
最长递增子序列问题
打家劫舍问题
背包问题
编辑距离问题
其他方法？
好！到这里可能有人会有疑惑，能不能用前缀和 + 排序 + 二分查找的方式来解呢？
这样复杂度也不高呀，好像也不错呢。。。
也就是
- 计算前缀和数组 prefixSum。
- 对于每个 prefixSum[j]，查找是否存在 prefixSum[i] = prefixSum[j] - k。
- 由于前缀和数组是无序的，需要先排序，然后使用二分查找。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
int n = nums.size();
vector<int> prefixSum(n + 1, 0);
for (int i = 1; i <= n; ++i) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
// 排序前缀和数组
sort(prefixSum.begin(), prefixSum.end());
// 二分查找
for (int j = 1; j <= n; ++j) {
int target = prefixSum[j] - k;
if (binary_search(prefixSum.begin(), prefixSum.end(), target)) {
count++;
}
}
return count;
}
};复杂度分析：
- 时间复杂度：O(n log n)，排序和二分查找的时间复杂度都是 O(n log n)。
- 空间复杂度：O(n)，用于存储前缀和数组。
但是实际上
很明显是不行的！！！
因为
排序前缀和数组：
前缀和数组 prefixSum 的排序会破坏前缀和的顺序关系，导致无法正确计算子数组和。
例如，假设 prefixSum = [0, 1, 3, 2]，排序后变为 [0, 1, 2, 3]，此时无法通过 prefixSum[j] - prefixSum[i] 来正确计算子数组和。
二分查找的逻辑错误：
即使排序后使用二分查找，也无法保证找到的 target = prefixSum[j] - k 是在 j 之前的前缀和。
例如，如果 prefixSum = [0, 1, 3, 2]，排序后为 [0, 1, 2, 3]，当 j = 3 时，target = 2 - k，但 2 可能是 prefixSum[2] 或 prefixSum[3]，无法确定其位置。
无法统计所有满足条件的子数组：
即使找到 target，也无法确定有多少个前缀和等于 target，因为排序后丢失了前缀和的顺序信息。
总结
除了本题的最优解之外，还深入的分析了其他方法的思路，希望各位能从一题中得到更多的启发