做网站卖大闸蟹,免费空间网站,wordpress 文章查看次数,wordpress 自动抓取给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1#xff1a;
输入#xff1a;nums [1,1,1], k 2 输出#xff1a;2 示例 2#xff1a;
输入#xff1a;nums [1,2,3],…给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1
输入nums [1,1,1], k 2 输出2 示例 2
输入nums [1,2,3], k 3 输出2
提示
1 nums.length 2 * 104 -1000 nums[i] 1000 -107 k 107
思路
看到想到是滑动窗口调了力扣结果和本地调的对不上看题解发现说有负值那滑动就不行。 官解是前缀和记一下。 其中关键代码是
count mp[pre - k]; // 如果存在前缀和为pre - k更新count表示如果mp中存在pre - k说明存在一个前缀和为pre - k那么从这个前缀和的末尾到当前索引的子数组和为k。即从pre - k前缀和的末尾到当前索引位置的子数组满足条件可被记录。 因此将count增加mp[pre - k]该前缀和出现的次数每个对应一种满足的情况。
代码
滑动窗口仅适合全为正 奇怪的点全为正的时候本地调是正确的力扣上结果就不对不知道哪儿有问题。
class Solution {
public:int subarraySum(vectorint nums, int k) {int sum0;int l0,r0;int cnt0;sort(nums.begin(),nums.end());if(knums[0])return cnt;while(rnums.size()){sumnums[r];while(sumk){if(sumk){cnt;}sum-nums[l]; }}return cnt;}
};前缀和
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint, int mp;mp[0] 1; // 初始化前缀和为0的出现次数为1int count 0, pre 0;for (auto x : nums) {pre x; // 更新前缀和count mp[pre - k]; // 如果存在前缀和为pre - k更新countmp[pre]; // 更新当前前缀和的出现次数}return count;}
};官解当中多一个判定
if (mp.find(pre - k) ! mp.end())可省略因为即使 mp[pre - k] 之前没有出现过其值也是0不会对 count 产生影响。
