双指针+前缀和习题（一步步讲解）

前言：如果解决下面这几道题有些问题，或者即使看了我画的过程图也不理解的可以去看看我的上一篇文章，有可能会对你有帮助。

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

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

这道题暴力解法思路很简单，在这不过多赘述，直接上代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr[N], brr[N];
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[i]);for (int i = 0; i < m; i++)scanf_s("%d", &brr[i]);for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (arr[i] + brr[j] == x){cout << i << " " << j << endl;exit(0);}}}return 0;
}

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

2.优化代码

1.画图分析

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

 双指针：上面是两种思路进行分析，选取最方便最可行的方式，也就是第二种

2.打代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr[N], brr[N];
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[i]);for (int i = 0; i < m; i++)scanf_s("%d", &brr[i]);for (int i = 0 , j = m-1; i < n ; i++){while (j >= 0 && arr[i] + brr[j] > x){j--;}if (arr[i] + brr[j] == 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.画图分析：

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

2.打代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int arr[N], cnt[N];
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[i]);for (int i = 0, j = 0; i < n; i++){while (j < n && arr[i] - arr[j] >= c){if (arr[i] - arr[j] == c){res++;}j++;}}cout << res << endl;return 0;
}

但是这样做是错误的。我们继续进行分析

3.进一步优化

重新找测试用例：

 

如果我画的图看不懂，可以自己尝试画一画，真的可以使自己的思路变得清晰明了

千万不要忘记排序！！！

 4.重新打代码

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int arr[N], cnt[N];
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[i]);sort(arr,arr+n);for (int i = 0, j1 = 0,j2 = 0; i < n; i++){while (j1 < n && arr[i] - arr[j1] >= c){j1++;}while (j2 < j1 && arr[i] - arr[j2] > c){ j2++;}res += (j1 - j2);}cout << res << endl;return 0;
}

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

给定三个整数数组 A=[A1,A2,⋯ ,AN]，B=[B1,B2,⋯ ,BN]，C=[C1,C2,⋯ ,CN]

请你统计有多少个三元组 (i,j,k)(i,j,k) 满足：

  1. 1≤i,j,k≤N
  2. 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[N], brr[N], crr[N];
int main(void)
{int n;cin >> n;for (int i = 1; i <= n; i++)cin >> arr[i];for (int i = 1; i <= n; i++)cin >> brr[i];for (int i = 1; i <= n; i++)cin >> crr[i];//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[i] < brr[j]&&brr[j] < crr[k])res++;}}}cout << res << endl;return 0;
}

2.优化代码

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

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

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n , a[N] , b[N] , c[N] , ans;
signed main(){cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) cin >> b[i];for(int i = 1; i <= n; i++) cin >> c[i];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[j]) - a - 1;int cntc = upper_bound(c + 1 , c + 1 + n , b[j]) - 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[N], brr[N], crr[N];
int n;
int binary1(int x)
{int l = 0, r = n + 1;while (l + 1 != r){int mid = (l + r) / 2;if (arr[mid] < brr[x])l = mid;else r = mid;}if (arr[l] < brr[x])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[mid] <= brr[x])l = mid;else r = mid;}if (crr[r] > brr[x])return r;else return -1;
}
int main(void)
{cin >> n;for (int i = 1; i <= n; i++)cin >> arr[i];for (int i = 1; i <= n; i++)cin >> brr[i];for (int i = 1; i <= n; i++)cin >> crr[i];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[N], b[N], c[N];
int main() {int n;cin >> n;for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);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[i]的个数和c中不大于b[i]的个数 for (int i = 1; i <= n; i ++ ){while (cnt <= n && a[cnt] < b[i]) cnt ++;//查找a中小于b[i]的个数 while (cnt_ <= n && c[cnt_] <= b[i]) cnt_ ++;//为了方便。实际是在查找c中大于b[i]的个数 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[N];
int n;
int main(void)
{cin >> n;for (int i = 1; i <= n; i++)cin >> arr[i];long long res = 0, tmp = 0;for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++){tmp += (arr[i] * arr[j]);res += tmp;}}cout << tmp << endl;return 0;
}

不过对于这道题来说，暴力解题只能得30分

2.前缀和解法

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

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int arr[N], s[N];
int n;
int main(void)
{cin >> n;long long res = 0;for (int i = 1; i <= n; i++){cin >> arr[i];s[i] = s[i-1] + arr[i];}for (int i = 1; i <= n; i++){res += (arr[i]*(long long)(s[n]-s[i]));//千万千万别忘记开long long}cout << res << endl;return 0;
}

 

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/6272.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

springboot 配置redis

springboot 配置redis

环境配置 springboot3.4 redis5.0.14 redis准备参考下面文章 window下安装redis以及启动 redis客户端安装 引入依赖 <!-- 集成redis依赖 --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-…
阅读更多...
TODO: Linux 中的装机硬件测试工具

TODO: Linux 中的装机硬件测试工具

TODO: Linux 中的装机硬件测试工具 装机时需要测一些硬件参数&#xff0c;希望选择一些跨平台的开源软件。 https://linux.do/t/topic/22175 https://www.baeldung-cn.com/linux/system-testing-tools https://blog.csdn.net/weixin_45358801/article/details/142701279
阅读更多...
LabVIEW 太阳能光伏发电系统智能监控

LabVIEW 太阳能光伏发电系统智能监控

本文介绍了基于 LabVIEW 的太阳能光伏发电监控系统的设计与实现&#xff0c;着重探讨了其硬件配置、软件架构以及系统的实现方法。该系统能够有效提高太阳能光伏发电的监控效率和精确性&#xff0c;实现了远程监控和数据管理的智能化。 ​ 项目背景 在当前能源紧张与环境污染…
阅读更多...
doris：Broker Load

doris：Broker Load

Broker Load 通过 MySQL API 发起&#xff0c;Doris 会根据 LOAD 语句中的信息&#xff0c;主动从数据源拉取数据。Broker Load 是一个异步导入方式&#xff0c;需要通过 SHOW LOAD 语句查看导入进度和导入结果。 Broker Load 适合源数据存储在远程存储系统&#xff0c;比如对…
阅读更多...
WPF5-x名称空间

WPF5-x名称空间

1. x名称空间2. x名称空间内容3. x名称空间内容分类 3.1. x:Name3.2. x:Key3.3. x:Class3.4. x:TypeArguments 4. 总结 1. x名称空间 “x名称空间”的x是映射XAML名称空间时给它取的名字&#xff08;取XAML的首字母&#xff09;&#xff0c;里面的成员&#xff08;如x:Class、…
阅读更多...
网站HTTP改成HTTPS

网站HTTP改成HTTPS

您不仅需要知道如何将HTTP转换为HTTPS&#xff0c;还必须在不妨碍您的网站自成立以来建立的任何搜索排名权限的情况下进行切换。 为什么应该从HTTP转换为HTTPS&#xff1f; 与非安全HTTP于不同&#xff0c;安全域使用SSL&#xff08;安全套接字层&#xff09;服务器上的加密代…
阅读更多...
煤矿场景下拖链检测数据集VOC+YOLO格式21407张1类别

煤矿场景下拖链检测数据集VOC+YOLO格式21407张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;21407 标注数量(xml文件个数)&#xff1a;21407 标注数量(txt文件个数)&#xff1a;2140…
阅读更多...
栈和队列（C语言）

栈和队列（C语言）

目录 数据结构之栈 定义 实现方式 基本功能实现 1&#xff09;定义&#xff0c;初始化栈 2&#xff09;入栈 3&#xff09;出栈 4&#xff09;获得栈顶元素 5)获得栈中有效元素个数 6&#xff09;检测栈是否为空 7&#xff09;销毁栈 数据结构之队列 定义 实现方…
阅读更多...
Flutter鸿蒙化中的Plugin

Flutter鸿蒙化中的Plugin

Flutter鸿蒙化中的Plugin 前言鸿蒙项目内PluginFlutter端实现鸿蒙端实现创建Plugin的插件类注册Plugin 开发纯Dart的package为现有插件项目添加ohos平台支持创建插件配置插件编写插件内容 参考资料 前言 大家知道Flutter和鸿蒙通信方式和Flutter和其他平台通信方式都是一样的&…
阅读更多...
探索JavaScript前端开发：开启交互之门的神奇钥匙（二）

探索JavaScript前端开发：开启交互之门的神奇钥匙（二）

目录 引言 四、事件处理 4.1 事件类型 4.2 事件监听器 五、实战案例&#xff1a;打造简易待办事项列表 5.1 HTML 结构搭建 5.2 JavaScript 功能实现 六、进阶拓展&#xff1a;异步编程与 Ajax 6.1 异步编程概念 6.2 Ajax 原理与使用 七、前沿框架&#xff1a;Vue.js …
阅读更多...
DeepSeek-R1：性能对标 OpenAI，开源助力 AI 生态发展

DeepSeek-R1：性能对标 OpenAI，开源助力 AI 生态发展

DeepSeek-R1&#xff1a;性能对标 OpenAI&#xff0c;开源助力 AI 生态发展 在人工智能领域&#xff0c;大模型的竞争一直备受关注。最近&#xff0c;DeepSeek 团队发布了 DeepSeek-R1 模型&#xff0c;并开源了模型权重&#xff0c;这一举动无疑为 AI 领域带来了新的活力。今…
阅读更多...
假期day1

假期day1

第一天&#xff1a;请使用消息队列实现2个终端之间互相聊天 singal1.c #include <stdio.h>#include <string.h>#include <unistd.h>#include <stdlib.h>#include <sys/types.h>#include <sys/stat.h>#include <fcntl.h>#include &l…
阅读更多...
go-zero框架基本配置和错误码封装

go-zero框架基本配置和错误码封装

文章目录 加载配置信息配置 env加载.env文件配置servicecontext 查询数据生成model文件执行查询操作 错误码封装配置拦截器错误码封装 接上一篇&#xff1a;《go-zero框架快速入门》 加载配置信息 配置 env 在项目根目录下新增 .env 文件&#xff0c;可以配置当前读取哪个环…
阅读更多...
考研机试：买房子

考研机试：买房子

描述 某程序员开始工作&#xff0c;年薪 N万&#xff0c;他希望在中关村公馆买一套 60平米的房子&#xff0c;现在价格是 200 万&#xff0c;假设房子价格以每年百分之 K 增长&#xff0c;并且该程序员未来年薪不变&#xff0c;且不吃不喝&#xff0c;不用交税&#xff0c;每年…
阅读更多...
Ansible fetch模块详解：轻松从远程主机抓取文件

Ansible fetch模块详解：轻松从远程主机抓取文件

在自动化运维的过程中&#xff0c;我们经常需要从远程主机下载文件到本地&#xff0c;以便进行分析或备份。Ansible的fetch模块正是为了满足这一需求而设计的&#xff0c;它可以帮助我们轻松地从远程主机获取文件&#xff0c;并将其保存到本地指定的位置。在这篇文章中&#xf…
阅读更多...
前端开发中的模拟后端与MVVM架构实践[特殊字符][特殊字符][特殊字符]

前端开发中的模拟后端与MVVM架构实践[特殊字符][特殊字符][特殊字符]

平时&#xff0c;后端可能不能及时给接口给前端进行数据调用和读取。这时候&#xff0c;前端想到进行模拟后端接口。本文将介绍如何通过vite-plugin-mock插件模拟后端接口&#xff0c;并探讨MVVM架构在前端开发中的应用。此外&#xff0c;我们还将讨论Vue2与Vue3的区别&#xf…
阅读更多...
JAVA毕业设计210—基于Java+Springboot+vue3的中国历史文化街区管理系统(源代码+数据库)

JAVA毕业设计210—基于Java+Springboot+vue3的中国历史文化街区管理系统(源代码+数据库)

毕设所有选题&#xff1a; https://blog.csdn.net/2303_76227485/article/details/131104075 基于JavaSpringbootvue3的中国历史文化街区管理系统(源代码数据库)210 一、系统介绍 本项目前后端分离(可以改为ssm版本)&#xff0c;分为用户、工作人员、管理员三种角色 1、用户…
阅读更多...
docker的前世今生

docker的前世今生

docker来自哪里&#xff1f; 从我们运维部署的历史来看&#xff0c;宿主机从最初的物理机到虚拟机&#xff0c;再到docker&#xff0c;一步步演进到现在。技术演进其实是为了解决当前技术的痛点&#xff0c;那我们来看看有哪些痛点以及如何克服痛点的。 物理机 一般来说&…
阅读更多...
电脑办公技巧之如何在 Word 文档中添加文字或图片水印

电脑办公技巧之如何在 Word 文档中添加文字或图片水印

Microsoft Word是全球最广泛使用的文字处理软件之一&#xff0c;它为用户提供了丰富的编辑功能来美化和保护文档。其中&#xff0c;“水印”是一种特别有用的功能&#xff0c;它可以用于标识文档状态&#xff08;如“草稿”或“机密”&#xff09;、公司标志或是版权信息等。本…
阅读更多...
【机器学习案列】探索各因素对睡眠时间影响的回归分析

【机器学习案列】探索各因素对睡眠时间影响的回归分析

&#x1f9d1; 博主简介&#xff1a;曾任某智慧城市类企业算法总监&#xff0c;目前在美国市场的物流公司从事高级算法工程师一职&#xff0c;深耕人工智能领域&#xff0c;精通python数据挖掘、可视化、机器学习等&#xff0c;发表过AI相关的专利并多次在AI类比赛中获奖。CSDN…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023