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

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

一、《数值元素的目标和》---来自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;
}

 

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

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

单路由及双路由端口映射指南

单路由及双路由端口映射指南

远程登录总会遇到登陆不上的情况&#xff0c;可能是访问的大门没有打开哦&#xff0c;下面我们来看看具体是怎么回事&#xff1f; 当软件远程访问时&#xff0c;主机需要两个条件&#xff0c;一是有一个唯一的公网IP地址&#xff08;运营商提供&#xff09;&#xff0c;二是开…
阅读更多...
Addressable学习

Addressable学习

AssetsBundle是Unity的资源管理机制,将资源打包到AssetsBundle资源包并提供接口能从ab包里面加载资源出来。有了这个机制以后&#xff0c;我们要做资源管理&#xff0c;还需要做: a: 根据项目需求,编写编辑器扩展,提供指定资源打入对应bundle包工具策略; b: 根据项目的需求,资源…
阅读更多...
大华相机DH-IPC-HFW3237M支持的ONVIF协议

大华相机DH-IPC-HFW3237M支持的ONVIF协议

使用libONVIF C库。 先发现相机。 配置 lib目录 包含 编译提示缺的文件&#xff0c;到libonvif里面拷贝过来。 改UDP端口 代码 使用msvc 2022的向导生成空项目&#xff0c;从项目的main示例拷贝过来。 CameraOnvif.h #pragma once#include <QObject> #include &l…
阅读更多...
leetcode刷题记录（八十六）——84. 柱状图中最大的矩形

leetcode刷题记录（八十六）——84. 柱状图中最大的矩形

&#xff08;一&#xff09;问题描述 84. 柱状图中最大的矩形 - 力扣&#xff08;LeetCode&#xff09;84. 柱状图中最大的矩形 - 给定 n 个非负整数&#xff0c;用来表示柱状图中各个柱子的高度。每个柱子彼此相邻&#xff0c;且宽度为 1 。求在该柱状图中&#xff0c;能够勾…
阅读更多...
centos9编译安装opensips 二【进阶篇-定制目录+模块】推荐

centos9编译安装opensips 二【进阶篇-定制目录+模块】推荐

环境&#xff1a;centos9 last opensips -V version: opensips 3.6.0-dev (x86_64/linux) flags: STATS: On, DISABLE_NAGLE, USE_MCAST, SHM_MMAP, PKG_MALLOC, Q_MALLOC, F_MALLOC, HP_MALLOC, DBG_MALLOC, CC_O0, FAST_LOCK-ADAPTIVE_WAIT ADAPTIVE_WAIT_LOOPS1024, MAX_RE…
阅读更多...
SpringBoot 实现动态管理定时任务 Job的动态操作（添加、修改、启停、执行、删除）以及界面展示和具体Job的创建与执行示例

SpringBoot 实现动态管理定时任务 Job的动态操作（添加、修改、启停、执行、删除）以及界面展示和具体Job的创建与执行示例

SpringBoot 实现动态管理定时任务 Job的动态操作&#xff08;添加、修改、启停、执行、删除&#xff09;以及界面展示和具体Job的创建与执行示例 关键接口类&#xff1a; CronTaskRegistrar SchedulingRunnable . 添加定时任务注册类&#xff0c;用来增加、删除定时任务 impo…
阅读更多...
LLMs的星辰大海：大语言模型的前世今生

LLMs的星辰大海：大语言模型的前世今生

文章目录 一. LLM 的演进&#xff1a;从规则到智能的跃迁 &#x1f4ab;1.1 语言模型的蹒跚起步 &#x1f476;1.2 RNN 与 LSTM&#xff1a;序列建模的尝试 &#x1f9d0;1.3 Transformer 的横空出世&#xff1a;自注意力机制的革命 &#x1f4a5;1.4 LLM &#xff1a;从预测到…
阅读更多...
路由器旁挂三层网络实现SDWAN互联(爱快SD-WAN)

路由器旁挂三层网络实现SDWAN互联(爱快SD-WAN)

近期因公司新办公区建设&#xff0c;原有的爱快路由器的SDWAN功能实现分支之间互联的服务还需要继续使用。在原有的小型网络中&#xff0c;使用的爱快路由器当作网关设备&#xff0c;所以使用较为简单,如下图所示。 现变更网络拓扑为三层网络架构&#xff0c;但原有的SDWAN分支…
阅读更多...
flutter_学习记录_00_环境搭建

flutter_学习记录_00_环境搭建

1.参考文档 Mac端Flutter的环境配置看这一篇就够了 flutter的中文官方文档 2. 本人环境搭建的背景 本人的电脑的是Mac的&#xff0c;iOS开发&#xff0c;所以iOS开发环境本身是可用的&#xff1b;外加Mac电脑本身就会配置Java的环境。所以&#xff0c;后面剩下的就是&#x…
阅读更多...
15_业务系统基类

15_业务系统基类

创建脚本 SystemRoot.cs 因为 业务系统基类的子类 会涉及资源加载服务层ResSvc.cs 和 音乐播放服务层AudioSvc.cs 所以在业务系统基类 提取引用资源加载服务层ResSvc.cs 和 音乐播放服务层AudioSvc.cs 并调用单例初始化 using UnityEngine; // 功能 : 业务系统基类 public c…
阅读更多...
docker 安装 redis 详解

docker 安装 redis 详解

在平常的开发工作中&#xff0c;我们经常会用到 redis&#xff0c;那么 docker 下应该如何安装 redis 呢&#xff1f;简单来说&#xff1a;第一步&#xff1a;拉取redis镜像&#xff1b;第二步&#xff1a;设置 redis.conf 配置文件&#xff1b;第三步&#xff1a;编写 docker-…
阅读更多...
困境如雾路难寻，心若清明步自轻---2024年创作回顾

困境如雾路难寻，心若清明步自轻---2024年创作回顾

文章目录 前言博客创作回顾第一次被催更第一次获得证书周榜几篇博客互动最多的最满意的引发思考的 写博契机 碎碎念时也运也部分经验 尾 前言 今年三月份&#xff0c;我已写下一篇《近一年多个人总结》&#xff0c;当时还没开始写博客。四月份写博后&#xff0c;就顺手将那篇总…
阅读更多...
综合与时序分析的设计约束（1）——静态时序分析简介

综合与时序分析的设计约束（1）——静态时序分析简介

目录 1.绪论2.静态时序分析与动态时序分析3.时序约束在静态时序分析中的作用3.1.约束作为声明3.2. 约束作为断言3.3.约束作为指令3.4.约束作为异常3.5.约束的角色变化 4.STA需要正确约束5.时序路径起点和终点6.建立与保持6.1 建立时间6.2 保持时间6.3 裕度 7.SDC主要类型7.1 时…
阅读更多...
【算法日记】从零开始认识动态规划（一）

【算法日记】从零开始认识动态规划（一）

挫折会来也会过去&#xff0c; 热泪会流下也会收起&#xff0c; 没有什么可以让我气馁的&#xff0c; 因为&#xff0c;我有着长长的一生。 --- 席慕蓉 《写给幸福》--- 从零开始认识动态规划 1 动态规划问题1.1 什么是动态规划算法1.2 动态规划算法如何Debug1.3 动态规划…
阅读更多...
八股学习 微服务篇

八股学习 微服务篇

微服务篇 常见面试内容Spring Cloud 常见组件注册中心Ribbon负载均衡策略服务雪崩 常见面试内容 Spring Cloud 常见组件 Spring Cloud有5个常见组件&#xff1a; Eureka/Nacos:注册中心&#xff1b;Ribbon:负载均衡&#xff1b;Feign:远程调用&#xff1b;Hystrix/Sentinel:服…
阅读更多...
【矢量数据】2024年最新中国省市县乡四级矢量地图数据 [推广有奖]

【矢量数据】2024年最新中国省市县乡四级矢量地图数据 [推广有奖]

中国四级矢量地图数据是当前地理信息系统&#xff08;GIS&#xff09;中广泛应用的重要资源&#xff0c;涉及国家级、省级、市级、县级及乡级行政区的空间信息。这些数据可应用于地图绘制、城市规划、政府决策及各类地理分析等领域 一、中国四级矢量地图数据的介绍 本分享数据…
阅读更多...
力扣707题（2）——设计链表

力扣707题（2）——设计链表

#题目 #3,5和6的代码 今天看剩下几个题的代码&#xff0c;1,2,4的代码已经在上篇博客写过了想看的小伙伴移步到&#xff1a; 力扣707题——设计链表-CSDN博客 //第3题头插法 void addAtHead(int val){ //记录头结点ListNode nhead; //新节点的创建,并让它指向原本头结点的后…
阅读更多...
JavaWeb 学习笔记 XML 和 Json 篇 | 020

JavaWeb 学习笔记 XML 和 Json 篇 | 020

今日推荐语 愿你遇见好天气,愿你的征途铺满了星星——圣埃克苏佩里 日期 学习内容 打卡编号2025年01月23日JavaWeb笔记 XML 和 Json 篇020 前言 哈喽&#xff0c;我是菜鸟阿康。 以下是我的学习笔记&#xff0c;既做打卡也做分享&#xff0c;希望对你也有所帮助…
阅读更多...
c#实现当捕获异常时自动重启程序

c#实现当捕获异常时自动重启程序

首先&#xff0c;需要说明这并不是一个推荐的做法&#xff0c;只有在你确实有这样的需求时才考虑这么做。 以下是AI的回答&#xff0c;为什么不推荐这么做&#xff0c;供参考。 在C#中&#xff0c;如果你在catch语句中尝试重启程序自身&#xff0c;可能会遇到以下几个问题&…
阅读更多...
Spring WebSocket 与 STOMP 协议结合实现私聊私信功能

Spring WebSocket 与 STOMP 协议结合实现私聊私信功能

目录 后端pom.xmlConfig配置类Controller类DTO 前端安装相关依赖websocketService.js接口javascripthtmlCSS 效果展示简单测试连接&#xff1a; 报错解决方法1、vue3 使用SockJS报错 ReferenceError: global is not defined 功能补充拓展1. 安全性和身份验证2. 异常处理3. 消息…
阅读更多...
最新文章

Copyright @ 2022~2023