算法分析
(双指针)
利用序列的单调性性质,使用双指针算法
- 1、
i
指针在A[]
数组从左往右扫,在扫的过程中,给定i位置,当A[i] + B[j] > x时
,j
指针在B[]
数组从右往左扫,
时间复杂度$O(m + n)$
参考文献
Java 代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int x = scan.nextInt();
int[] A = new int[n];
int[] B = new int[m];
for(int i = 0;i < n;i++) A[i] = scan.nextInt();
for(int j = 0;j < m;j++) B[j] = scan.nextInt();
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) System.out.println(i +" " + j);
}
}
}