Problem: 560. 和为 K 的子数组
LeetCode 560. 和为K的子数组题解
题目描述
给定一个整数数组 nums 和一个整数 k，要求返回数组中和为 k 的连续子数组的个数。子数组是数组中连续的非空元素序列。
示例
- 输入：nums = [1, 1, 1], k = 2
- 输出：2
这是一个经典的前缀和应用场景，同时通过不停优化，我们可以从O(N³)的暴力解法提拔到O(N)的哈希表解法。下面，我们分阶段具体讲解不同解法的逐步优化。
方法一：暴力解法
思路
- 枚举所有可能的子数组出发点和终点，盘算每个子数组的和是否等于 k。
- 三重循环：
- 外层循环固定出发点 left。
- 第二层循环选择不同的终点 right。
- 内层循环盘算 [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[i];
- }
- if (sum == k) {
- count++;
- }
- }
- }
- return count;
- }
- };
方法二：暴力解法优化
思路
- 进一步优化暴力解法，将最内层的求和操纵提前到第二层，避免重复求和。
- 固定左边界，右边界扩展过程中累加盘算区间和，从而降低一个维度的循环。
实现
- 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[right];
- if (sum == k) {
- count++;
- }
- }
- }
- return count;
- }
- };
方法三：前缀和
思路
- 构建前缀和数组，用于快速盘算区间和，避免手动求和。
- 前缀和数组界说为 preSum，表现 nums[0] 到 nums[i-1] 的和。
- 通过公式 preSum[right+1] - preSum[left] == 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[i + 1] = preSum[i] + nums[i];
- }
- int count = 0;
- for (int left = 0; left < len; left++) {
- for (int right = left; right < len; right++) {
- if (preSum[right + 1] - preSum[left] == k) {
- count++;
- }
- }
- }
- return count;
- }
- };
方法四：前缀和 + 哈希表优化
思路
- 由于只关心区间和等于 k 的个数，可以使用哈希表记录前缀和的出现次数。
- 假设当前前缀和为 preSum，那么我们必要查找是否有之前的前缀和满意 preSum - k。
- 每当找到满意条件的 preSum - k，阐明存在一个区间和为 k 的子数组。
实现
- class Solution {
- public:
- int subarraySum(vector<int>& nums, int k) {
- unordered_map<int, int> prefixSumCount;
- prefixSumCount[0] = 1;
- int preSum = 0;
- int count = 0;
-
- for (int num : nums) {
- preSum += num;
- if (prefixSumCount.find(preSum - k) != prefixSumCount.end()) {
- count += prefixSumCount[preSum - k];
- }
- prefixSumCount[preSum]++;
- }
- return count;
- }
- };
解题思路（详解）：前缀和 + 哈希表
1. 前缀和概念
前缀和是一种方便盘算数组区间和的方法，假设我们有一个数组 nums，prefixSum 表现从数组开始到 i 的元素之和，那么对于数组恣意区间 [j, i]，其和就可以表现为：
[ \text{sum}([j, i]) = \text{prefixSum} - \text{prefixSum}[j-1] ]
我们可以通过这个前缀和的头脑，判断从某个起始点 j 到 i 的子数组是否满意和为 k。
2. 使用哈希表存储前缀和出现的次数
我们用一个哈希表 prefixSumCount 来记录每个前缀和的出现次数，这样可以在常数时间内查找是否存在一个前缀和满意条件。
设当前的前缀和为 currentSum，则要找到的满意条件的前缀和 targetSum 应该是：
[ \text{targetSum} = \text{currentSum} - k ]
如果 targetSum 在哈希表中存在，阐明从这个 targetSum 之后到当前的 currentSum 之间的子数组和为 k，这样就可以统计符合条件的子数组。
3. 具体步调
- 初始化：我们将 prefixSumCount[0] = 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[0] = 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[currentSum - k]; // 加上满足条件的前缀和出现的次数
- }
- // 更新哈希表，记录当前前缀和的出现次数
- prefixSumCount[currentSum]++;
- }
- return count; // 返回和为 k 的子数组数量
- }
- };
示例详解
示例 1
输入：nums = [1, 1, 1], 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企服之家，中国第一个企服评测及商务社交产业平台。 |
