560. 和为 K 的子数组
题目
给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的子数组的个数。
子数组是数组中元素的连续非空序列。
示例 1：
- 输入：
nums = [1,1,1],k = 2 - 输出：
2
示例 2：
- 输入：
nums = [1,2,3],k = 3 - 输出：
2
提示：
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
代码
完整代码
代码1
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>int subarraySum(int* nums, int numsSize, int k) {int count = 0;int prefixSum = 0;int minPrefixSum = 0;int maxPrefixSum = 0;// 计算所有可能的前缀和的最小值和最大值for (int i = 0; i < numsSize; i++) {prefixSum += nums[i];if (prefixSum < minPrefixSum) {minPrefixSum = prefixSum;}if (prefixSum > maxPrefixSum) {maxPrefixSum = prefixSum;}}// 计算哈希表的大小并分配内存int size = maxPrefixSum - minPrefixSum + 1;int* prefixSumCount = (int*)calloc(size, sizeof(int));if (!prefixSumCount) {return -1; // 内存分配失败}// 初始化prefixSumCount[-minPrefixSum] = 1; // 对应于前缀和为0的情况prefixSum = 0;// 遍历数组，计算前缀和并更新哈希表for (int i = 0; i < numsSize; i++) {prefixSum += nums[i];int target = prefixSum - k;if (target >= minPrefixSum && target <= maxPrefixSum) {count += prefixSumCount[target - minPrefixSum];}prefixSumCount[prefixSum - minPrefixSum]++;}// 释放内存free(prefixSumCount);return count;
}
代码2
int subarraySum(int* nums, int numsSize, int k) {if (numsSize == 1) {if (nums[0] != k) return 0;else return 1;}int* pHead = nums;int* pEnd = nums + 1;int cnt = (*pHead) == k;int nowSum = *pHead;while (pEnd < nums + numsSize) {nowSum += *pEnd;if (nowSum == k) {cnt++;}pEnd++;if ((pEnd == nums + numsSize) /* 到了数组末尾 */ && (pHead != nums + numsSize - 1) /* 头节点不在数组末尾 */) {pHead++;pEnd = pHead + 1;nowSum = *pHead;cnt += ((*pHead) == k);}}return cnt;
}
思路分析
对于这道题，我们需要统计数组中和为 k 的子数组个数。可以用前缀和加哈希表的方法，也可以用双指针法。下面详细介绍这两种方法。
方法一：前缀和 + 哈希表
-
初始化变量：
count用于记录和为k的子数组个数。prefixSum用于记录当前前缀和。minPrefixSum和maxPrefixSum用于记录前缀和的最小值和最大值。
-
计算前缀和的范围：
- 遍历数组，计算所有可能的前缀和的最小值和最大值。
-
使用哈希表存储前缀和出现的次数：
- 计算哈希表的大小，并分配内存。
- 初始化哈希表，对应前缀和为 0 的情况。
- 遍历数组，计算前缀和并更新哈希表。
-
统计和为
k的子数组个数：- 如果
target在前缀和的范围内，则累加count。 - 更新当前前缀和的计数。
- 如果
-
释放内存。
方法二：双指针法
-
初始化指针和变量：
- 使用两个指针
pHead和pEnd。 - 变量
cnt用于记录和为k的子数组个数。 - 变量
nowSum用于记录当前子数组的和。
- 使用两个指针
-
遍历数组：
- 使用双指针遍历数组，计算子数组的和。
- 如果当前子数组和为
k，则累加cnt。 - 当遍历到数组末尾且
pHead不在数组末尾时，移动pHead，并更新pEnd和nowSum。
-
返回结果。
复杂度分析
方法一：前缀和 + 哈希表
- 时间复杂度：O(n)，其中 n 是数组的长度。我们遍历数组两次，第一次计算前缀和范围，第二次更新哈希表并统计结果。
- 空间复杂度：O(n)，我们使用了一个哈希表来存储前缀和的次数。
方法二：双指针法
- 时间复杂度：
O(n^2)，其中n是数组的长度。最坏情况下，双指针遍历数组的时间复杂度为O(n^2)。 - 空间复杂度：
O(1)，我们只使用了常量级别的额外空间。
结果
方案1
方案2
