双指针+前缀和习题（一步步教学）

媒介：如果解决下面这几道题有些题目，大概纵然看了我画的过程图也不明白的可以去看看我的上一篇文章，有大概会对你有资助。

---

一、《数值元素的目标和》---来自AcWing  

   数组元素的目标和
给定两个升序排序的有序数组 A和 B，以及一个目标值 。
数组下标从 0 开始。
请你求出满足 A+ B[j]=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.暴力解法

这道题暴力解法思绪很简朴，在这不外多赘述，直接上代码：

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. const int N = 1e5 + 10;
5. int arr[N], brr[N];
6. int n, m, x;
7. int main(void)
8. {
9.         scanf_s("%d%d%d", &n, &m, &x);
10.         for (int i = 0; i < n; i++)scanf_s("%d", &arr[i]);
11.         for (int i = 0; i < m; i++)scanf_s("%d", &brr[i]);
12.         for (int i = 0; i < n; i++)
13.         {
14.                 for (int j = 0; j < m; j++)
15.                 {
16.                         if (arr[i] + brr[j] == x)
17.                         {
18.                                 cout << i << " " << j << endl;
19.                                 exit(0);
20.                         }
21.                 }
22.         }
23.         return 0;
24. }

复制代码

分析暴力算法的时间复杂度：很明显O(n的平方)，数组长度最大是1e5,以是时间复杂度准确为O(1e10),大于1e9，以是要开始想办法优化代码。
2.优化代码

1.绘图分析

（看过我前面的文章的都知道我习惯用绘图来疏通自己的思维逻辑）

 双指针：上面是两种思绪进行分析，选取最方便最可行的方式，也就是第二种
2.打代码

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. const int N = 1e5 + 10;
5. int arr[N], brr[N];
6. int n, m, x;
7. int main(void)
8. {
9.         scanf_s("%d%d%d", &n, &m, &x);
10.         for (int i = 0; i < n; i++)scanf_s("%d", &arr[i]);
11.         for (int i = 0; i < m; i++)scanf_s("%d", &brr[i]);
12.         for (int i = 0 , j = m-1; i < n ; i++)
13.         {
14.                 while (j >= 0 && arr[i] + brr[j] > x)
15.                 {
16.                         j--;
17.                 }
18.                 if (arr[i] + brr[j] == x)
19.                 {
20.                         cout << i << " " << j << endl;
21.                         return 0;
22.                 }
23.         }
25.         return 0;
26. }

复制代码

仔细琢磨while循环所表达的意思，对照我所画的图进行分析，信任明白把握这道题并不难
二、A-B数对---来自洛谷

   给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数（差别位置的数字一样的数对算差别的数对）。
  输入格式：
  输入共两行。
  第一行，两个正整数 N,C。
  第二行，N 个正整数，作为要求处理的那串数
  输特别式：
  一行，体现该串正整数中包罗的满足 A−B=C 的数对的个数。
  输入样例：
  4 1
  1 1  2 3
  输出样例：
  3
  1.暴力解法

2.优化代码

1.绘图分析：

跟上个题一样，双指针的两种方式，从两个角度进行分析。

2.打代码

1. #include<iostream>
2. #include<algorithm>
3. #include<cmath>
4. using namespace std;
5. using ll = long long;
6. const int N = 2e5 + 10;
7. int arr[N], cnt[N];
8. ll n, c;
9. int main(void)
10. {
11.         scanf_s("%lld%lld", &n, &c);
12.         ll res = 0;
13.         for (int i = 0; i < n; i++)scanf_s("%d", &arr[i]);
14.         for (int i = 0, j = 0; i < n; i++)
15.         {
16.                 while (j < n && arr[i] - arr[j] >= c)
17.                 {
18.                         if (arr[i] - arr[j] == c)
19.                         {
20.                                 res++;
21.                         }
22.                         j++;
23.                 }
24.                
25.         }
26.         cout << res << endl;
27.         return 0;
28. }

复制代码

但是这样做是错误的。我们继承进行分析
3.进一步优化

重新找测试用例：

 

如果我画的图看不懂，可以自己尝试画一画，真的可以使自己的思绪变得清楚明白
万万不要忘记排序！！！
 4.重新打代码

1. #include<iostream>
2. #include<algorithm>
3. #include<cmath>
4. using namespace std;
5. using ll = long long;
6. const int N = 2e5 + 10;
7. int arr[N], cnt[N];
8. ll n, c;
9. int main(void)
10. {
11.         scanf_s("%lld%lld", &n, &c);
12.         ll res = 0;
13.         for (int i = 0; i < n; i++)scanf_s("%d", &arr[i]);
14.     sort(arr,arr+n);
15.         for (int i = 0, j1 = 0,j2 = 0; i < n; i++)
16.         {
17.                 while (j1 < n && arr[i] - arr[j1] >= c)
18.                 {
19.                         j1++;
20.                 }
21.                 while (j2 < j1 && arr[i] - arr[j2] > c)
22.                 {
23.                         j2++;
24.                 }
25.                 res += (j1 - j2);
26.                
27.         }
28.         cout << res << endl;
29.         return 0;
30. }

复制代码

三、递增三元组---来自洛谷

   给定三个整数数组 A=[A1,A2,⋯ ,AN]，B=[B1,B2,⋯ ,BN]，C=[C1,C2,⋯ ,CN]
  请你统计有多少个三元组 (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
  输特别式：
  一个整数体现答案
  输入样例：

1. 3
2. 1 1 1
3. 2 2 2
4. 3 3 3

复制代码

输出样例：
  27
  1.暴力解法

思绪也是很简朴，三层循环摆列就可以

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. const int N = 1e5 + 10;
5. int arr[N], brr[N], crr[N];
6. int main(void)
7. {
8.         int n;
9.         cin >> n;
10.         for (int i = 1; i <= n; i++)cin >> arr[i];
11.         for (int i = 1; i <= n; i++)cin >> brr[i];
12.         for (int i = 1; i <= n; i++)cin >> crr[i];
13.         //sort(arr + 1, arr + n + 1);
14.         //sort (brr + 1, brr + 1 + n);
15.         //sort(crr + 1, crr + 1 + n);
16.         long long res = 0;
17.         for (int i = 1; i <= n; i++)
18.         {
19.                 for (int j = 1; j <= n; j++)
20.                 {
21.                         for (int k = 1; k <= n; k++)
22.                         {
23.                                 if (arr[i] < brr[j]&&brr[j] < crr[k])res++;
24.                         }
25.                 }
26.         }
27.         cout << res << endl;
28.         return 0;
29. }

复制代码

2.优化代码

1.可以用二分查找来解决

这里我不多说关于二分的解题过程，照旧将过程图画出来，大家感兴趣的可以看看，代码我也会给大家

1. #include <bits/stdc++.h>
2. #define int long long
3. using namespace std;
4. const int N = 1e5 + 5;
5. int n , a[N] , b[N] , c[N] , ans;
6. signed main(){
7.         cin >> n;
8.         for(int i = 1; i <= n; i++) cin >> a[i];
9.         for(int i = 1; i <= n; i++) cin >> b[i];
10.         for(int i = 1; i <= n; i++) cin >> c[i];
11.         sort(a + 1 , a + 1 + n);
12.         sort(c + 1 , c + 1 + n);
13.         //排序，好进行二分
14.         for(int j = 1; j <= n; j++){
15.                 int cnta = lower_bound(a + 1 , a + 1 + n , b[j]) - a - 1;
16.                 int cntc = upper_bound(c + 1 , c + 1 + n , b[j]) - c;
17.                 cntc = n - cntc + 1;
18.                 //二分找出i的种类数和j的种类数
19.                 ans += cnta * cntc;//乘法原理累计答案
20.         }
21.         cout << ans;
22.         return 0;
23. }

复制代码

自界说如下： 

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. const int N = 1e5 + 10;
5. int arr[N], brr[N], crr[N];
6. int n;
7. int binary1(int x)
8. {
9.         int l = 0, r = n + 1;
10.         while (l + 1 != r)
11.         {
12.                 int mid = (l + r) / 2;
13.                 if (arr[mid] < brr[x])l = mid;
14.                 else r = mid;
15.         }
16.         if (arr[l] < brr[x])return l;
17.         else return -1;
18. }
19. int binary2(int x)
20. {
21.         int l = 0, r = n + 1;
22.         while (l + 1 != r)
23.         {
24.                 int mid = (l + r) / 2;
25.                 if (crr[mid] <= brr[x])l = mid;
26.                 else r = mid;
27.         }
28.         if (crr[r] > brr[x])return r;
29.         else return -1;
30. }
31. int main(void)
32. {
33.         cin >> n;
34.         for (int i = 1; i <= n; i++)cin >> arr[i];
35.         for (int i = 1; i <= n; i++)cin >> brr[i];
36.         for (int i = 1; i <= n; i++)cin >> crr[i];
37.         sort(arr + 1, arr + n + 1);
38.         sort(brr + 1, brr + 1 + n);
39.         sort(crr + 1, crr + 1 + n);
40.         long long res = 0, tmp = 0;
41.         for (int i = 1; i <= n; i++)
42.         {
43.                 int x = binary1(i);
44.                 int y = binary2(i);
45.                 if (x == -1 || y == -1)continue;
46.                 else
47.                 {
48.                         tmp = (long long)((x) * (n - y + 1));
49.                         res += tmp;
50.                 }
51.         }
52.         cout << res << endl;
53.         return 0;
54. }

复制代码

2.用双指针来解决

想必认真做了前面两道题的同学，这道题绘图之后也会有些思绪，看一看自己写的和我写的有什么差别，及时订正！

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 1e5 + 5;
4. typedef long long LL;
5. int a[N], b[N], c[N];
6. int main() {
7.     int n;
8.     cin >> n;
9.     for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
10.     for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
11.     for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
12.     sort(a + 1, a + n + 1);
13.     sort(b + 1, b + n + 1);
14.     sort(c + 1, c + n + 1);//先把数组排序，否则无法双指针
15.     LL ans = 0;//不开long long见祖宗
16.     int cnt = 1, cnt_ = 1;
17.     //双指针，记录a中小于b[i]的个数和c中不大于b[i]的个数
18.     for (int i = 1; i <= n; i ++ ){
19.         while (cnt <= n && a[cnt] < b[i]) cnt ++;//查找a中小于b[i]的个数
20.         while (cnt_ <= n && c[cnt_] <= b[i]) cnt_ ++;//为了方便。实际是在查找c中大于b[i]的个数
21.         ans += (LL) (cnt - 1) * (n - cnt_ + 1);
22.     }
23.     cout << ans;
24.     return 0;
25. }

复制代码

 四、求和----来自洛谷

   题目描述：
  给定 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，体现所求的和。请使用符合的数据类型进行运算。
  输入输出样例
  输入：

1. 4
2. 1 3 6 9

复制代码

输出 ：

1. 117

复制代码

对于 30% 的数据, 1≤n≤1000,1≤ai≤100 。
  对于所有评测用例, 1≤n≤2×1e5,1≤ai≤1000 。
  1.暴力解法

这道题的暴力解法就是两层循环，照旧不外多赘述：

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. const int N = 2e5 + 10;
5. int arr[N];
6. int n;
7. int main(void)
8. {
9.         cin >> n;
10.         for (int i = 1; i <= n; i++)cin >> arr[i];
11.         long long res = 0, tmp = 0;
12.         for (int i = 1; i <= n; i++)
13.         {
14.                 for (int j = i + 1; j <= n; j++)
15.                 {
16.                         tmp += (arr[i] * arr[j]);
17.                         res += tmp;
18.                 }
19.         }
20.         cout << tmp << endl;
21.         return 0;
22. }

复制代码

不外对于这道题来说，暴力解题只能得30分
2.前缀和解法

很明显：我们只要知道怎样求S[n]就能很完美的做出这道题 S[n]的求解就用到了前缀和算法头脑

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
4. const int N = 2e5 + 10;
5. int arr[N], s[N];
6. int n;
7. int main(void)
8. {
9.         cin >> n;
10.         long long res = 0;
11.         for (int i = 1; i <= n; i++)
12.         {
13.                 cin >> arr[i];
14.                 s[i] = s[i-1] + arr[i];
15.         }
16.         for (int i = 1; i <= n; i++)
17.         {
18.                 res += (arr[i]*(long long)(s[n]-s[i]));//千万千万别忘记开long long
19.         }
20.         cout << res << endl;
22.         return 0;
23. }

复制代码

 

---

最后：真心渴望这篇文章对你有所资助！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。