LeetCode 热题100——560.和为K的子数组

题目给你一个整数数组nums和一个整数k请你统计并返回该数组中和为k的子数组的个数。子数组是数组中元素的连续非空序列。示例 1输入nums [1,1,1], k 2输出2示例 2输入nums [1,2,3], k 3输出2提示1 nums.length 2 * 10^4-1000 nums[i] 1000-10^7 k 10^7题解最直观的暴力做法是枚举所有子数组计算和并判断是否等于 k时间复杂度为 O(n^2)会超时。利用前缀和可以将子数组和转换为两个前缀和的差把问题转化一下我们要找和为 k 的子数组即前 r1 个数的和 - 前 l 个数的和 k移项得前 l 个数的和 前 r1 个数的和 - k这就变成了当我们走到某个位置算出当前前缀和 pre时只要看看 之前有没有出现过前缀和等于 pre - k如果有则有多少个这样的前缀就找到多少个子数组。我们使用一个哈希表 mp 来记录每个前缀和出现的次数遍历过程中实时更新答案。答案class Solution { public: int subarraySum(vectorint nums, int k) { int ans0; int pre0;// pre: 当前前缀和 unordered_mapint,int mp; // 哈希表键→前缀和值→该前缀和出现的次数 mp[0]1;// 初始化前缀和为0出现1次表示空数组 for(auto x:nums){ prex; //查找之前是否存在前缀和为 pre - k 的记录 if(mp.find(pre-k)!mp.end()) {//找到了 ansmp[pre-k];// 有多少个这样的前缀就找到多少个子数组 } mp[pre];// 将当前前缀和加入哈希表供后续使用 } return ans; } };要点1.为什么初始化 mp[0] 1当 pre k 时pre - k 0此时需要从哈希表中取出 0 的个数。0 代表空数组的前缀和它对应了从数组开头到当前位置的子数组。因此必须提前将 0 的计数设为 1。2.为什么先查找再插入查找的是之前出现过的前缀和不包括当前 pre 本身。如果先插入当前 pre当 k 0 时pre - k pre就会错误地将当前子数组长度为 0也算进去导致多计数。正确顺序先查询历史再将当前前缀和存入哈希表。