（10）LeetCode 560. 和为K的子数组

LeetCode 560. 和为K的子数组题目描述给你一个整数数组nums和一个整数k请你统计并返回该数组中和为k的连续子数组的个数。示例 1输入nums [1,1,1], k 2 输出2示例 2输入nums [1,2,3], k 3 输出2解题思路1. 问题转化假设我们定义前缀和pre[i]为数组nums[0..i]的和即pre[i] nums[0] nums[1] ... nums[i]。那么对于任意一个连续子数组nums[j..i]j ≤ i它的和可以表示为sum(j, i) pre[i] - pre[j-1]当j 0时规定pre[-1] 0。题目要求sum(j, i) k即pre[i] - pre[j-1] k→pre[j-1] pre[i] - k。因此对于每个以i结尾的子数组我们只需要知道在i之前包括i自身吗注意j-1 i所以是之前有多少个位置j-1的前缀和等于pre[i] - k。这些位置对应的j就是以i结尾且和为k的子数组的起点。2. 哈希表优化我们可以用一个哈希表hash来记录遍历过程中每个前缀和出现的次数遍历数组依次计算当前前缀和cur。对于当前cur我们想要知道之前出现过的cur - k有多少次这些次数就是当前i结尾的满足条件的子数组个数累加到答案中。然后将当前前缀和cur的次数加 1供后续使用。初始化hash[0] 1非常重要。它表示在数组开始之前即下标-1处有一个虚拟的前缀和为 0。这样当某个cur k时cur - k 0就能从哈希表中取到 1从而正确统计从下标 0 到 i 的这个子数组。3. 代码实现细节原代码将原数组原地修改为前缀和数组节省了空间。遍历一次并同时更新哈希表和答案。代码实现CclassSolution{public:intsubarraySum(vectorintnums,intk){intnnums.size(),ans0;// 将原数组转化为前缀和数组原地修改for(inti1;in;i)nums[i]nums[i-1];unordered_mapint,inthash;// 记录每个前缀和出现的次数hash[0]1;// 初始化前缀和为0出现1次空子数组for(inti0;in;i){// 当前前缀和减去k得到需要的前缀和值anshash[nums[i]-k];// 将当前前缀和的计数加1hash[nums[i]];}returnans;}};复杂度分析时间复杂度O(n)其中n是数组的长度。我们只需遍历数组两次一次计算前缀和一次遍历统计哈希表的插入和查询都是O(1)。空间复杂度O(n)哈希表在最坏情况下需要存储所有不同的前缀和。总结本题是前缀和与哈希表结合的经典题目。核心思想是将子数组和问题转化为两个前缀和的差值问题利用哈希表快速查找之前出现过的前缀和从而在一次遍历中完成统计。初始化hash[0] 1是处理从数组开头开始的子数组的关键。拓展如果题目要求返回所有满足条件的子数组的具体下标则可以在哈希表中存储前缀和对应的下标列表然后遍历输出。如果数组中有负数前缀和可能不是单调的但该算法依然适用因为哈希表只关心值出现的次数不关心顺序。