【LeetCode每日一题】——560.和为 K 的子数组
一【题目类别】
- 前缀和
二【题目难度】
- 中等
三【题目编号】
- 560.和为 K 的子数组
四【题目描述】
- 给你一个整数数组
nums
和一个整数k
,请你统计并返回 该数组中和为k
的子数组的个数 。 - 子数组是数组中元素的连续非空序列。
五【题目示例】
-
示例 1:
- 输入:nums = [1,1,1], k = 2
- 输出:2
-
示例 2:
- 输入:nums = [1,2,3], k = 3
- 输出:2
六【题目提示】
- 1 < = n u m s . l e n g t h < = 2 ∗ 1 0 4 1 <= nums.length <= 2 * 10^4 1<=nums.length<=2∗104
- − 1000 < = n u m s [ i ] < = 1000 -1000 <= nums[i] <= 1000 −1000<=nums[i]<=1000
- − 1 0 7 < = k < = 1 0 7 -10^7 <= k <= 10^7 −107<=k<=107
七【解题思路】
- 使用前缀和+哈希表解决该问题
- 前缀和都很清楚了,那么如何与哈希表结合在一起呢?
- 在本题中,我们使用哈希表记录当前前缀和的出现次数
- 在每次得到新的前缀和时,就去哈希表中找“当前前缀和 - k”的值对应的次数,“当前前缀和 - k”对应的就是“之前前缀和”
- 这样,我们就找到满足“之前前缀和 + 当前前缀和 = k”的子数组,即和为 K 的子数组
- 通过这种方法,可以有效地降低时间复杂度
- 最后返回结果即可
- 具体细节可以参考下面的代码
八【时空频度】
- 时间复杂度: O ( n ) O(n) O(n), n n n为传入的数组的长度
- 空间复杂度: O ( n ) O(n) O(n), n n n为传入的数组的长度
九【代码实现】
- Java语言版
class Solution {
public int subarraySum(int[] nums, int k) {
// 初始化哈希表,前缀和为0的情况为1次
HashMap<Integer, Integer> hashMap = new HashMap<>();
hashMap.put(0, 1);
// 记录满足条件的子数组个数
int count = 0;
// 初始化前缀和
int prefixSum = 0;
for (int num : nums) {
// 计算当前的前缀和
prefixSum += num;
// 检查是否存在 prefix_sum - k 的前缀和
if (hashMap.containsKey(prefixSum - k)) {
// 加上满足条件的前缀和个数
count += hashMap.get(prefixSum - k);
}
// 更新哈希表中的当前前缀和出现次数
hashMap.put(prefixSum, hashMap.getOrDefault(prefixSum, 0) + 1);
}
return count;
}
}
- Python语言版
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
# 初始化哈希表,前缀和为0的情况为1次
hash_map = {0 : 1}
# 记录满足条件的子数组个数
count = 0
# 初始化前缀和
prefix_sum = 0
for num in nums:
# 计算当前的前缀和
prefix_sum += num
# 检查是否存在 prefix_sum - k 的前缀和
if prefix_sum - k in hash_map:
# 加上满足条件的前缀和个数
count += hash_map[prefix_sum - k]
# 更新哈希表中的当前前缀和出现次数
hash_map[prefix_sum] = hash_map.get(prefix_sum, 0) + 1
return count
- C++语言版
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
// 初始化哈希表,前缀和为0的情况为1次
unordered_map<int, int> hashMap;
hashMap[0] = 1;
// 记录满足条件的子数组个数
int count = 0;
// 初始化前缀和
int prefixSum = 0;
for (int num : nums) {
// 计算当前的前缀和
prefixSum += num;
// 检查是否存在 prefix_sum - k 的前缀和
if (hashMap.find(prefixSum - k) != hashMap.end()) {
// 加上满足条件的前缀和个数
count += hashMap[prefixSum - k];
}
// 更新哈希表中的当前前缀和出现次数
hashMap[prefixSum]++;
}
return count;
}
};
十【提交结果】
-
Java语言版
-
Python语言版
-
C++语言版
原文地址:https://blog.csdn.net/IronmanJay/article/details/143077096
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!