双指针+前缀和习题（一步步教学）
媒介：如果解决下面这几道题有些题目，大概纵然看了我画的过程图也不明白的可以去看看我的上一篇文章，有大概会对你有资助。一、《数值元素的目标和》---来自AcWing
数组元素的目标和
给定两个升序排序的有序数组 A和 B，以及一个目标值 。
数组下标从 0 开始。
请你求出满足 A+ B=x 的数对(i,j)。
数据保证有唯一解。
输入格式:
第一行包罗三个整数 n,m,x，分别体现 A 的长度，B 的长度以及目标值。
第二行包罗 n 个整数，体现数组 A。
第三行包罗 m 个整数，体现数组 B.
输特别式:
共一行，包罗两个整数i和 j.
数据范围:
数组长度不凌驾 1e5
同一数组内元素各不相同。
1 ≤ 数组元素 < 1e9
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1
1.暴力解法
这道题暴力解法思绪很简朴，在这不外多赘述，直接上代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr, brr;
int n, m, x;
int main(void)
{
scanf_s("%d%d%d", &n, &m, &x);
for (int i = 0; i < n; i++)scanf_s("%d", &arr);
for (int i = 0; i < m; i++)scanf_s("%d", &brr);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (arr + brr == x)
{
cout << i << " " << j << endl;
exit(0);
}
}
}
return 0;
} 分析暴力算法的时间复杂度：很明显O(n的平方)，数组长度最大是1e5,以是时间复杂度准确为O(1e10),大于1e9，以是要开始想办法优化代码。
2.优化代码
1.绘图分析
（看过我前面的文章的都知道我习惯用绘图来疏通自己的思维逻辑）
https://i-blog.csdnimg.cn/direct/ca8972a56f1b4abfb175814cea2872ee.png
双指针：上面是两种思绪进行分析，选取最方便最可行的方式，也就是第二种
2.打代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr, brr;
int n, m, x;
int main(void)
{
scanf_s("%d%d%d", &n, &m, &x);
for (int i = 0; i < n; i++)scanf_s("%d", &arr);
for (int i = 0; i < m; i++)scanf_s("%d", &brr);
for (int i = 0 , j = m-1; i < n ; i++)
{
while (j >= 0 && arr + brr > x)
{
j--;
}
if (arr + brr == x)
{
cout << i << " " << j << endl;
return 0;
}
}
return 0;
} 仔细琢磨while循环所表达的意思，对照我所画的图进行分析，信任明白把握这道题并不难
二、A-B数对---来自洛谷
给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数（差别位置的数字一样的数对算差别的数对）。
输入格式：
输入共两行。
第一行，两个正整数 N,C。
第二行，N 个正整数，作为要求处理的那串数
输特别式：
一行，体现该串正整数中包罗的满足 A−B=C 的数对的个数。
输入样例：
4 1
1 1 2 3
输出样例：
3
1.暴力解法
2.优化代码
1.绘图分析：
跟上个题一样，双指针的两种方式，从两个角度进行分析。
https://i-blog.csdnimg.cn/direct/323672de387d450da37d3df0d15316f6.png
2.打代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int arr, cnt;
ll n, c;
int main(void)
{
scanf_s("%lld%lld", &n, &c);
ll res = 0;
for (int i = 0; i < n; i++)scanf_s("%d", &arr);
for (int i = 0, j = 0; i < n; i++)
{
while (j < n && arr - arr >= c)
{
if (arr - arr == c)
{
res++;
}
j++;
}
}
cout << res << endl;
return 0;
} 但是这样做是错误的。我们继承进行分析
3.进一步优化
重新找测试用例：
https://i-blog.csdnimg.cn/direct/4e42dc26b98f4bc89deb7086fb5239c7.png
https://i-blog.csdnimg.cn/direct/b5162a6575a54ed4af3d5536e0b003e7.png
如果我画的图看不懂，可以自己尝试画一画，真的可以使自己的思绪变得清楚明白
万万不要忘记排序！！！
4.重新打代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int arr, cnt;
ll n, c;
int main(void)
{
scanf_s("%lld%lld", &n, &c);
ll res = 0;
for (int i = 0; i < n; i++)scanf_s("%d", &arr);
sort(arr,arr+n);
for (int i = 0, j1 = 0,j2 = 0; i < n; i++)
{
while (j1 < n && arr - arr >= c)
{
j1++;
}
while (j2 < j1 && arr - arr > c)
{
j2++;
}
res += (j1 - j2);
}
cout << res << endl;
return 0;
} 三、递增三元组---来自洛谷
给定三个整数数组 A=，B=，C=
请你统计有多少个三元组 (i,j,k)(i,j,k) 满足：
[*]1≤i,j,k≤N
[*]Ai<Bj<Ck
输入格式：
第一行包罗一个整数 N。
第二行包罗 N 个整数 A1,A2,⋯ ,AN
第三行包罗 N 个整数 B1,B2,⋯ ,BN
第四行包罗 N 个整数 C1,C2,⋯ ,CN
输特别式：
一个整数体现答案
输入样例：
3
1 1 1
2 2 2
3 3 3输出样例：
27
1.暴力解法
思绪也是很简朴，三层循环摆列就可以
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr, brr, crr;
int main(void)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)cin >> arr;
for (int i = 1; i <= n; i++)cin >> brr;
for (int i = 1; i <= n; i++)cin >> crr;
//sort(arr + 1, arr + n + 1);
//sort (brr + 1, brr + 1 + n);
//sort(crr + 1, crr + 1 + n);
long long res = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
if (arr < brr&&brr < crr)res++;
}
}
}
cout << res << endl;
return 0;
} 2.优化代码
1.可以用二分查找来解决
这里我不多说关于二分的解题过程，照旧将过程图画出来，大家感兴趣的可以看看，代码我也会给大家
https://i-blog.csdnimg.cn/direct/dc81e4ea40a2490abe5423cd060d16fe.png
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n , a , b , c , ans;
signed main(){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a;
for(int i = 1; i <= n; i++) cin >> b;
for(int i = 1; i <= n; i++) cin >> c;
sort(a + 1 , a + 1 + n);
sort(c + 1 , c + 1 + n);
//排序，好进行二分
for(int j = 1; j <= n; j++){
int cnta = lower_bound(a + 1 , a + 1 + n , b) - a - 1;
int cntc = upper_bound(c + 1 , c + 1 + n , b) - c;
cntc = n - cntc + 1;
//二分找出i的种类数和j的种类数
ans += cnta * cntc;//乘法原理累计答案
}
cout << ans;
return 0;
} 自界说如下：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr, brr, crr;
int n;
int binary1(int x)
{
int l = 0, r = n + 1;
while (l + 1 != r)
{
int mid = (l + r) / 2;
if (arr < brr)l = mid;
else r = mid;
}
if (arr < brr)return l;
else return -1;
}
int binary2(int x)
{
int l = 0, r = n + 1;
while (l + 1 != r)
{
int mid = (l + r) / 2;
if (crr <= brr)l = mid;
else r = mid;
}
if (crr > brr)return r;
else return -1;
}
int main(void)
{
cin >> n;
for (int i = 1; i <= n; i++)cin >> arr;
for (int i = 1; i <= n; i++)cin >> brr;
for (int i = 1; i <= n; i++)cin >> crr;
sort(arr + 1, arr + n + 1);
sort(brr + 1, brr + 1 + n);
sort(crr + 1, crr + 1 + n);
long long res = 0, tmp = 0;
for (int i = 1; i <= n; i++)
{
int x = binary1(i);
int y = binary2(i);
if (x == -1 || y == -1)continue;
else
{
tmp = (long long)((x) * (n - y + 1));
res += tmp;
}
}
cout << res << endl;
return 0;
} 2.用双指针来解决
想必认真做了前面两道题的同学，这道题绘图之后也会有些思绪，看一看自己写的和我写的有什么差别，及时订正！
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
int a, b, c;
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i ++ ) scanf("%d", &a);
for (int i = 1; i <= n; i ++ ) scanf("%d", &b);
for (int i = 1; i <= n; i ++ ) scanf("%d", &c);
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
sort(c + 1, c + n + 1);//先把数组排序，否则无法双指针
LL ans = 0;//不开long long见祖宗
int cnt = 1, cnt_ = 1;
//双指针，记录a中小于b的个数和c中不大于b的个数
for (int i = 1; i <= n; i ++ ){
while (cnt <= n && a < b) cnt ++;//查找a中小于b的个数
while (cnt_ <= n && c <= b) cnt_ ++;//为了方便。实际是在查找c中大于b的个数
ans += (LL) (cnt - 1) * (n - cnt_ + 1);
}
cout << ans;
return 0;
} 四、求和----来自洛谷
题目描述：
给定 n 个整数 a1,a2,⋯ ,an, 求它们两两相乘再相加的和，即
S=a1⋅a2+a1⋅a3+⋯+a1⋅an+a2⋅a3+⋯+an−2⋅an−1+an−2⋅an+an−1⋅an
输入格式：
输入的第一行包罗一个整数 nn 。
第二行包罗 n 个整数 a1,a2,⋯an
输特别式：
输出一个整数 S，体现所求的和。请使用符合的数据类型进行运算。
输入输出样例
输入：
4
1 3 6 9输出 ：
117对于 30% 的数据, 1≤n≤1000,1≤ai≤100 。
对于所有评测用例, 1≤n≤2×1e5,1≤ai≤1000 。
1.暴力解法
这道题的暴力解法就是两层循环，照旧不外多赘述：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int arr;
int n;
int main(void)
{
cin >> n;
for (int i = 1; i <= n; i++)cin >> arr;
long long res = 0, tmp = 0;
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
tmp += (arr * arr);
res += tmp;
}
}
cout << tmp << endl;
return 0;
} 不外对于这道题来说，暴力解题只能得30分
2.前缀和解法
https://i-blog.csdnimg.cn/direct/5aa5e00c8f7e453aa6c84862f28fa024.png
很明显：我们只要知道怎样求S就能很完美的做出这道题 S的求解就用到了前缀和算法头脑
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int arr, s;
int n;
int main(void)
{
cin >> n;
long long res = 0;
for (int i = 1; i <= n; i++)
{
cin >> arr;
s = s + arr;
}
for (int i = 1; i <= n; i++)
{
res += (arr*(long long)(s-s));//千万千万别忘记开long long
}
cout << res << endl;
return 0;
}
最后：真心渴望这篇文章对你有所资助！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]