【Hot 100 刷题计划】 LeetCode 560. 和为 K 的子数组 | C++ 前缀和+哈希表题解

LeetCode 560. 和为 K 的子数组 | C 前缀和哈希表题解 题目描述题目级别中等给你一个整数数组nums和一个整数k请你统计并返回 该数组中和为k的子数组的个数。注子数组是数组中元素的连续非空序列。 解题思路前缀和 哈希表这道题如果使用暴力双重循环去枚举所有子数组时间复杂度会达到O(N2)O(N^2)O(N2)在数据量大的时候必然会超时。我们需要借助前缀和以及**两数之和哈希表**的思想来将时间复杂度优化到O(N)O(N)O(N)。1. 什么是前缀和假设pre[i]表示数组从下标0到下标i的所有元素之和。那么任意一段子数组nums[j...i]的和就可以表示为sum(j,i)pre[i]−pre[j−1]sum(j, i) pre[i] - pre[j - 1]sum(j,i)pre[i]−pre[j−1]题目要求找到和为kkk的子数组即pre[i]−pre[j−1]kpre[i] - pre[j - 1] kpre[i]−pre[j−1]k做一个简单的移项就变成了pre[j−1]pre[i]−kpre[j - 1] pre[i] - kpre[j−1]pre[i]−k2. 哈希表的作用上面的公式告诉我们当我们遍历数组计算出当前位置的前缀和pre[i]pre[i]pre[i]时我们只需要去历史记录里找前面有多少个前缀和等于pre[i]−kpre[i] - kpre[i]−k那么以当前节点为结尾的、和为kkk的子数组就有多少个我们使用一个哈希表unordered_mapint, int mp来记录Key: 前缀和的值Value: 该前缀和出现的次数3. 灵魂一步初始化mp[0] 1这是这道题极其重要的一步代表着“前缀和为 0 的情况出现了 1 次”。为什么要有这一步因为如果当前元素本身或者从数组头部到当前位置的这段前缀刚好加起来等于kkk那么pre[i]−kpre[i] - kpre[i]−k就会等于 0。如果不提前把mp[0]设为 1这种从头开始的有效子数组就会被漏掉。 C 代码实现classSolution{public:intsubarraySum(vectorintnums,intk){// mp 记录 前缀和, 该前缀和出现的次数unordered_mapint,intmp;// 核心初始化为了处理从数组头部开始且和为 k 的子数组mp[0]1;intsum0;// 记录当前的前缀和intres0;// 记录符合条件的子数组个数for(inti0;inums.size();i){// 更新当前位置的前缀和sumnums[i];// 如果之前出现过前缀和为 sum - k 的位置// 说明从那个位置到当前位置的子数组和刚好为 kif(mp.count(sum-k)){resmp[sum-k];}// 将当前的前缀和加入哈希表供后续的元素查询mp[sum];}returnres;}};