知识框架

No.0 筑基

请先学习下知识点，道友！
题目知识点大部分来源于此：前缀和

题目例题大部分来源于此：

No.1 普通前缀和

题目来源：牛客网-NC14556：数圈圈

题目描述：

题目思路：

题目代码：

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1001000
long long n,m,t,k,d;
long long x,y,z;
char ch;
string str;
vector<int>v[N];
int num[10]={1,0,0,0,1,0,1,0,2,1}; //0~9
int onum[N+1];
int s[N+1];
void Init(){for(int i=1;i<=N;i++){str=to_string(i);for(auto ss:str){int num1=ss-'0';onum[i]+=num[num1];}}s[1]=0;for(int i=2;i<=N;i++){s[i]=s[i-1]+onum[i];}
}
int main()
{Init();cin>>n;for(int i=0;i<n;i++){cin>>x>>y;cout<<s[y]-s[x-1]<<endl;}return 0;
}

题目来源：牛客网-NC14600：珂朵莉与宇宙

题目描述：

题目思路：

题目代码：

//巧妙地利用求平方 变化为减去平方看差是否存在：
//通过指针的指向，那么一串数组中的任意子区间就可以用 两个前缀和 进行 相减 得到：#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,t,k,d;
long long x,y,z,c;
char ch;
string str;
vector<int>v[N];
int s[N+1];int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>x;s[i]=s[i-1]+x;}int res=0;int cnt[N];cnt[0]=1;    //前缀和为0的表示 直接前面n个为平方和了//以每一个右边的端点为指针for(int i=1;i<=n;i++){//找到所有可能的平方和：//处理第i个前缀和的所有完全平方数for(int j=0;j*j<=s[i];j++){c=s[i]-j*j;         //假设前面有前缀和==c的； 即if(cnt[c]>0){       //如果前面有前缀和==c的 代表有子区间为j*j；res+=cnt[c];}}cnt[ s[i] ]++;   // 已处理过的这个端点，加入到cnt里面  表示前面的 前缀和为s[i] 的前缀和的个数加一}cout<<res;return 0;
}

题目来源：牛客网-NC21195 ：Kuangyeye and hamburgers

题目描述：

题目思路：

题目代码：

//vector 的 排序 比如降序：  sort(v.rbegin(),v.rend());
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,t,k,d;
long long x,y,z,c;
char ch;
string str;
vector<int>v[N];
int s[N+1]={0};int main()
{cin>>n>>m;vector<int>ans;for(int i=1;i<=n;i++){cin>>x;ans.push_back(x);}sort(ans.rbegin(),ans.rend());for(int i=0;i<ans.size();i++){s[i+1]=s[i]+ans[i];}int res=0;while(m--){cin>>x>>y;res=max(res,s[y]-s[x-1]);}cout<<res<<endl;return 0;
}

题目来源：牛客网-NC19798：区间权值

题目描述：

题目思路：

题目代码：

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,t,k,d;
long long x,y,z,c;
char ch;
string str;
vector<int>v[N];
int s[N+1]={0};
int w[N+1];
int leijia(int l,int r){return (s[r]-s[l-1])*w[r-l+1];
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>x;s[i]=s[i-1]+x;}for(int i=1;i<=n;i++){cin>>w[i];}//下面这个双层循环了导致时间复杂度很高：long long res=0;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){res=res+leijia(i,j);}}//将 j 的那部分再进行前缀和：因此要把过程改写：for(int j=1;j<=n;j++){}cout<<res%(1000000000+7);return 0;
}

题目来源：牛客网-NC15035：送分了qaq

经典基础：对x经行分位数处理，直到没有位数

#include<stdio.h>
int check(int x)
{int t=0;while(x > 0)//对x经行分位数处理，直到没有位数{if(x % 10 == 3){return 1；//如果已经有1接下来的位数便不用再判断了，直接可以return 1了}x /= 10;}return 0;
}

#include <stdio.h>
int main()
{int m,n;while(scanf("%d%d",&n,&m)!=EOF){if (m == 0 && n == 0)break;int ans=0;for(int i=n;i<=m;i++){int x=i;while(x){if(x%10==4||x%100==38) {ans++;break;}x/=10;}}printf("%d\\n",ans);}} 

No.3 leetcode的之前做的前缀和

【动画模拟】一文秒杀七道题 - 连续的子数组和 - 力扣（LeetCode）

前缀和+哈希表

要想着变化方程式，，比如哈希表的那个 pre[i] - pre[j-1] = k 变化为 pre[i] - k ; 找存在。

滑动窗口模板

滑动窗口是什么呢？ 可能是 一个start指针，一个end指针，进而进行滑动，根据一些题目条件进行移动。。

《挑战程序设计竞赛》这本书中把滑动窗口叫做「虫取法」，我觉得非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动。

我分享一个滑动窗口的模板，能解决大多数的滑动窗口问题：

def findSubArray(nums):N = len(nums) # 数组/字符串长度left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数res = 0 # 保存最大的满足题目要求的 子数组/子串 长度while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数while 区间[left, right]不符合题意: # 此时需要一直移动左指针，直至找到一个符合题意的区间sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反# 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串res = max(res, right - left + 1) # 需要更新结果right += 1 # 移动右指针，去探索新的区间return res

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：

1. 定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 sums 用来统计该区间内的各个字符出现次数；

2. 第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的求和/计数；

3. 第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left 每次移动到了新位置，需要减少 left 指针的求和/计数；

4. 在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，题目要求最大的区间长度，因此更新 res 为 max(res, 当前区间的长度) 。

5. right 指针每次向右移动一步，开始探索新的区间。

6. 模板中的 sums 需要根据题目意思具体去修改，本题是求和题目因此把sums 定义成整数用于求和；如果是计数题目，就需要改成字典用于计数。当左右指针发生变化的时候，都需要更新 sums

209. 长度最小的子数组：滑动窗口

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;int start = 0, end = 0;int sum = 0;while (end < n) {sum += nums[end];while (sum >= s) {ans = min(ans, end - start + 1);sum -= nums[start];start++;}end++;}return ans == INT_MAX ? 0 : ans;}
};

238. 除自身以外数组的乘积 前缀和+后缀和

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n=nums.size();int sumq[n];int sumh[n];for(int i=0;i<n;i++){if(i==0)sumq[i]=nums[i];else sumq[i]=sumq[i-1]*nums[i];}for(int i=n-1;i>=0;i--){if(i==n-1)sumh[i]=nums[i];else sumh[i]=sumh[i+1]*nums[i];}vector<int>ans;ans.push_back(sumh[1]);for(int i=1;i<n-1;i++){ans.push_back(sumq[i-1]*sumh[i+1]);}ans.push_back(sumq[n-2]);return ans;}
};

1004. 最大连续1的个数 III：滑动窗口

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oGuEapDr-1679671888186)(D:/Typora/images/image-20221020153751247.png)]

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n=nums.size();int left = 0,right=0,sum=0;int res=0;for( ;right<n;right++){if(nums[right]==0)sum++;while(sum>k){if(nums[left]==0)sum--;left++;}res=max(res,right-left+1);}return res;}
};

1124. 表现良好的最长时间段：前缀和+单调栈

// 首先尝试滑动窗口 进行 求解，，但是不行，只能通过一半。
//我一开始也以为是滑动窗口，但想这样的case：[1,2,3,9,9,9,9,9];类似这样的滑窗做不了
class Solution {
public:int longestWPI(vector<int>& hours) {int n=hours.size();int left=0,right=0,sum1=0;int res=0;for(;right<n;right++){if(hours[right]>8)sum1++;else sum1--;while(sum1<=0&&left<=right){if(sum1<=0&&left==right)break;if(hours[left]>8)sum1--;else sum1++;left++;}res=max(res,right-left+1);}return res;}
};// 下面的有点偏暴力了
class Solution {
public:int longestWPI(vector<int>& hours) {int n=hours.size();int sum[n];int nums[n];for(int i=0;i<n;i++){if(hours[i]>8)nums[i]=1;else nums[i]=-1;}sum[0]=nums[0];for(int i=1;i<n;i++){sum[i]=nums[i]+sum[i-1];}int left=0,right=0,sum1=0;int res=0;for(int i=0;i<n;i++){for(int j=i;j<n;j++){if(sum[j]-sum[i]+nums[i]>0){   //特别是这个判断条件的  +nums[i]res=max(res,j-i+1);}}}return res;}
};

724. 寻找数组的中心下标：前缀和

class Solution {
public:int pivotIndex(vector<int>& nums) {int n=nums.size();int sum[n+1];sum[0]=0;for(int i=0;i<n;i++){sum[i+1]=sum[i]+nums[i];}vector<int>ans;for(int i=1;i<=n;i++){int left = sum[i-1];int right = sum[n]-sum[i];if(left==right){ans.push_back(i-1);}}if(ans.size()==0)return -1;else return ans[0];}
};

560. 和为 K 的子数组：前缀和+哈希表

思路：其实我们现在这个题目和两数之和原理是一致的，只不过我们是将所有的前缀和该前缀和出现的次数存到了 map 里。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ikxzAXnr-1679671888186)(D:/Typora/images/image-20221025191243786.png)]

class Solution {
public:int subarraySum(vector<int>& nums, int k) {map<int,int>mp;mp[0]=1;//是从开始到自身即pre[i]-k=0;即int n=nums.size();int pre[n+1];pre[0]=0;int res=0;for(int i=1;i<=n;i++){pre[i]=pre[i-1]+nums[i-1];if(mp.find(pre[i]-k)!=mp.end()){res+=mp[pre[i]-k];}mp[pre[i]]++;}return res;}
};

1248. 统计「优美子数组」:前缀和+哈希表

思路”要想着变化方程式；；；

class Solution {
public:int numberOfSubarrays(vector<int>& nums, int k) {int res=0;int n=nums.size();int pre[n+1];pre[0]=0;map<int,int>mp;mp[0]=1;for(int i=0;i<n;i++){if(nums[i]%2==0){nums[i]=0;}else{nums[i]=1;}}for(int i=1;i<=n;i++){pre[i]=pre[i-1]+nums[i-1];if(mp.find(pre[i]-k)!=mp.end()){res+=mp[pre[i]-k];}mp[pre[i]]++;}return res;}
};

974. 和可被 K 整除的子数组：前缀和+哈希表

其中 巧妙的 还是 方程变化。 以及对 负数的处理。

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {map<int,int>mp;mp[0]=1;int n=nums.size();int pre[n+1];pre[0]=0;int res=0;for(int i=1;i<=n;i++){// 注意负数 的问题。pre[i]=pre[i-1]+nums[i-1];if(mp.find((pre[i]%k+k)%k)!=mp.end()){res+=mp[(pre[i]%k+k)%k];}mp[(pre[i]%k+k)%k]++;}return res;}
};

523. 连续的子数组和：前缀和+哈希表

class Solution {
public:bool checkSubarraySum(vector<int>& nums, int k) {int n = nums.size();map<int,int>mp;mp[0]=1;int pre[n+1];pre[0]=0;int res = 0;pre[1]=pre[0]+nums[0];for(int i=2;i<=n;i++){pre[i]=pre[i-1]+nums[i-1];if(mp.find(pre[i]%k)!=mp.end()){res+=mp[pre[i]%k];}mp[pre[i-1]%k]++; // 因为个数限制。}if(res==0)return false;else return true;}
};

930. 和相同的二元子数组：前缀和+哈希表

class Solution {
public:int numSubarraysWithSum(vector<int>& nums, int goal) {map<int,int>mp;mp[0]=1;int n=nums.size();int pre[n+1];pre[0]=0;int res=0;for(int i=1;i<=n;i++){pre[i]=pre[i-1]+nums[i-1];if(mp.find(pre[i]-goal)!=mp.end()){res+=mp[pre[i]-goal];}mp[pre[i]]++;           }return res;}
};

904. 水果成篮：滑动窗口+哈希表

class Solution {
public:int totalFruit(vector<int>& fruits) {int res = 0;int n =fruits.size();int right=0,left=0;set<int>sc;map<int,int>mp;for(;right<n;right++){sc.insert(fruits[right]);mp[fruits[right]]++;while(sc.size()>2){mp[fruits[left]]--;if(mp[fruits[left]]==0)sc.erase(fruits[left]);left++;}res=max(res,right-left+1);}return res;}
};

1]=pre[0]+nums[0];
for(int i=2;i<=n;i++){
pre[i]=pre[i-1]+nums[i-1];
if(mp.find(pre[i]%k)!=mp.end()){
res+=mp[pre[i]%k];
}
mp[pre[i-1]%k]++; // 因为个数限制。
}
if(res==0)return false;
else return true;

}

};

## [930. 和相同的二元子数组](https://leetcode.cn/problems/binary-subarrays-with-sum/)：前缀和+哈希表```c++
class Solution {
public:int numSubarraysWithSum(vector<int>& nums, int goal) {map<int,int>mp;mp[0]=1;int n=nums.size();int pre[n+1];pre[0]=0;int res=0;for(int i=1;i<=n;i++){pre[i]=pre[i-1]+nums[i-1];if(mp.find(pre[i]-goal)!=mp.end()){res+=mp[pre[i]-goal];}mp[pre[i]]++;           }return res;}
};

904. 水果成篮：滑动窗口+哈希表

class Solution {
public:int totalFruit(vector<int>& fruits) {int res = 0;int n =fruits.size();int right=0,left=0;set<int>sc;map<int,int>mp;for(;right<n;right++){sc.insert(fruits[right]);mp[fruits[right]]++;while(sc.size()>2){mp[fruits[left]]--;if(mp[fruits[left]]==0)sc.erase(fruits[left]);left++;}res=max(res,right-left+1);}return res;}
};