印刷设计营销网站,优化建立生育支持政策体系,国家企业信用信息公示信息查询网,wordpress 命令插件目录 数组元素的目标和思路#xff1a;暴力做法思路#xff1a;双指针做法#xff1a; 代码: 原题链接 数组元素的目标和
给定两个升序排序的有序数组 A 和 B #xff0c;以及一个目标值 x 。
数组下标从 0 开始。
请你求出满足 A[i]B[j]x 的数对 (i,j) 。
数据保证有唯… 目录 数组元素的目标和思路暴力做法思路双指针做法 代码: 原题链接 数组元素的目标和
给定两个升序排序的有序数组 A 和 B 以及一个目标值 x 。
数组下标从 0 开始。
请你求出满足 A[i]B[j]x 的数对 (i,j) 。
数据保证有唯一解。
输入格式 第一行包含三个整数 n,m,x 分别表示 A 的长度B 的长度以及目标值 x 。
第二行包含 n 个整数表示数组 A 。
第三行包含 m 个整数表示数组 B 。
输出格式 共一行包含两个整数 i 和 j 。
数据范围 数组长度不超过 105 。 同一数组内元素各不相同。 1≤数组元素≤109 输入样例 4 5 6 1 2 4 7 3 4 6 8 9 输出样例 1 1
思路
本题和上一题的思路差不多可以先思考一种暴力的做法再从暴力做法上面去优化
暴力做法思路
循环遍历两个数组 查看两个数组 相加是否为目标数 如果是目标 res;
双指针做法
利用两个数组都是有序的性质 一个指针A指向第一个数组头部另一个指针B指向第二个数组的尾部 让指针B指向最小的那一个 即 让 BA目标数字 的那个 每次遍历指针A指向的数字和指针B指向数字相加 后面A 数字变大 那么B只能–让数字变小来满足条件即此做法的时间复杂度为O(N)
代码:
#include iostream
#include cstdio
using namespace std;const int N 1e5 10;int n, m, k;
int a[N], b[N];
#define read(x) scanf(%d,x)int main()
{read(n), read(m), read(k);for (int i 0; i n; i ) read(a[i]);for (int i 0; i m; i ) read(b[i]);for (int i 0, j m - 1; i n; i ) {while(j 0 a[i] b[j] k) j --;if(j 0 a[i] b[j] k) printf(%d %d\n, i, j);}return 0;
}
