网站的发布方案有哪些,wordpress 付费文章,江西住房和城乡建设部网站,用什么网站开发多指针滑动窗口 滑动窗口#xff0c;由于题目中数组为二元组数组#xff0c;对于每一个数组下标 j #xff0c;当其满足 preSum[j]−preSum[i]goal的条件时#xff0c;对应 i为一个连续区间#xff0c;若能够求得 i 的左右边界 left1 与 left2#xff0c;则此时共有 left…多指针滑动窗口 滑动窗口由于题目中数组为二元组数组对于每一个数组下标 j 当其满足 preSum[j]−preSum[i]goal的条件时对应 i为一个连续区间若能够求得 i 的左右边界 left1 与 left2则此时共有 left2−left1个子数组满足条件。
因此构建一个滑动窗口随着其右边界 j 右移其相应的两个左边界 left1与 left2也会随之移动。在移动过程中我们要找到这两个左边界使得 [left1,left2) 区间内任一数组下标 i 到 滑动窗口的右边界j 的子数组之和为 goal。两个左边界通过窗口之和 sum1与 sum2 求取当窗口之和 sum1 大于目标值时left1 右移。当窗口之和 sum2 大于等于目标值时left2 右移。
class Solution {
public:int numSubarraysWithSum(vectorint nums, int goal) {int res0;int left10,left20,right0,nnums.size();long long tmp10,tmp20;while(rightn){tmp1nums[right];tmp2nums[right];right;while(left1right tmp1goal){tmp1-nums[left1];left1; }while(left2right tmp2goal){tmp2-nums[left2];left2;}resleft2-left1;}return res;}
};前缀和hash 不过空间复杂度O(n)
class Solution {
public:int numSubarraysWithSum(vectorint nums, int goal) {int nnums.size();int preSum0,res0;unordered_mapint,intmp;mp[0]1;for(int i0;in;i){preSumnums[i];resmp[preSum-goal];mp[preSum];}return res;}
};
