题目描述
blablabla
样例
blablabla
算法1
(双指针算法) $O(n)$
blablabla
时间复杂度
O(n)
参考文献
java 代码
import java.util.Scanner;
class Main {
public static void main(String []argv) {
final int N = 100010;
int n, m, tar;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
tar = sc.nextInt();
int []num1 = new int [N];
int []num2 = new int [N];
for(int i = 0; i < n; i ++)
num1[i] = sc.nextInt();
for(int i = 0; i < m; i ++)
num2[i] = sc.nextInt();
for(int i = 0, j = m - 1; i < n; i ++) {
while(j > 0 && num2[j] + num1[i] > tar) j --;
if(num1[i] + num2[j] == tar)
System.out.printf("%d %d", i, j);
}
}
}
算法2
(二分) $O(nlogn)$
blablabla
时间复杂度
O(nlogn)
参考文献
C++ 代码
#include<iostream>
using namespace std;
const int N = 100010;
int a[N],b[N];
int n,m,x;
int main()
{
cin >> n >> m >> x;
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<m;i++) cin >> b[i];
for(int i=0,j=m-1;i<n;i++)
{
while(j>=0&&a[i]+b[j]>x) j--;
if(a[i]+b[j]==x) cout << i << ' '<< j;
}
return 0;
}