【LeetCode每日一题】——560.和为 K 的子数组_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<=nums[i]<=1000$
• − 1 0 7 < = k < = 1 0 7 -10^7 <= k <= 10^7 −107<=k<=107

七【解题思路】

• 使用前缀和+哈希表解决该问题
• 前缀和都很清楚了，那么如何与哈希表结合在一起呢？
  • 在本题中，我们使用哈希表记录当前前缀和的出现次数
  • 在每次得到新的前缀和时，就去哈希表中找“当前前缀和 - k”的值对应的次数，“当前前缀和 - k”对应的就是“之前前缀和”
  • 这样，我们就找到满足“之前前缀和 + 当前前缀和 = k”的子数组，即和为 K 的子数组
• 通过这种方法，可以有效地降低时间复杂度
• 最后返回结果即可
• 具体细节可以参考下面的代码

八【时空频度】

• 时间复杂度：$O(n)$，$n$为传入的数组的长度
• 空间复杂度：$O(n)$，$n$为传入的数组的长度

九【代码实现】

1. 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; }}

2. 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

3. 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; }};

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C++语言版