【LeetCode】560.和为K的子数组

目录 题目题目要求什么是子数组？ 解法 前缀和 + 哈希表核心思路具体步骤 代码

题目

题目链接：LeetCode-560题

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。

题目要求 子数组是数组中元素的连续非空序列统计和为 k 的子数组的个数 什么是子数组？

子数组是数组中连续的一段元素组成的序列。例如，数组 [1, 2, 3] 的子数组包括 [1]、[2]、[3]、[1, 2]、[2, 3] 和 [1, 2, 3]。

解法 前缀和 + 哈希表 核心思路

如何快速统计和为 k 的子数组？

前缀和是一种常用的技巧，用于快速计算任意子数组的和。 我们需要找到所有满足 sum(nums[i…j]) = k 的子数组。根据前缀和的性质，可以转化为 dp[j] - dp[i-1] = k //前缀和-前缀和

即：

dp[j] - k = dp[i-1]

换句话说，我们需要找到所有满足 dp[j] - k 等于某个前缀和dp[i-1] 的情况。

哈希表的引入 为了快速查找是否存在某个前缀和，我们可以使用哈希表来记录前缀和出现的次数。 具体步骤

1.初始化：

使用哈希表 记录前缀和出现的次数。初始时，hash[0] = 1，表示前缀和为 0 的情况出现了一次,这样可以使刚好等于k的数字成为一个子数组。

初始化 sum 为 0，用于记录当前的前缀和。

初始化 count 为 0，用于记录满足条件的子数组的个数。

2.遍历数组：

对于数组中的每一个元素 num，更新sum，即 sum += num。

检查 sum - k 是否在哈希表中。如果在，则说明存在若干个子数组的和为 k，将这些子数组的数量累加到 count 中。

更新哈希表，将当前前缀和 currentSum 的出现次数加一。

代码 class Solution { public: unordered_map<int,int> hash; int ret = 0; int subarraySum(vector<int>& nums, int k) { hash[0] = 1; //为了使得一个数也可以成为一个数组 //前缀和 int sum = 0; for(int i = 0;i<nums.size();i++) { sum+=nums[i]; if(hash.count(sum-k)) ret+=hash[sum-k]; hash[sum]++; } return ret; } };