給定兩個升序排序的有序陣列A和B，以及一個目標值x，陣列下標從0開始，
請你求出滿足A[i] + B[j] = x的數對(i, j)，
資料保證有唯一解，
輸入格式
第一行包含三個整數n，m，x，分別表示A的長度，B的長度以及目標值x，
第二行包含n個整數，表示陣列A，
第三行包含m個整數，表示陣列B，
輸出格式
共一行，包含兩個整數 i 和 j，
資料范圍
陣列長度不超過100000，
同一陣列內元素各不相同，
1≤數組元素≤1091≤陣列元素≤109
輸入樣例：
4 5 6
1 2 4 7
3 4 6 8 9
輸出樣例：
1 1
思路：因為資料有唯一解，并且陣列有序；所以可以給兩個陣列兩個指標，一個陣列指標在頭，一個陣列指標在尾；兩個指標向中間移動，直到和等于x為止
代碼：
import java.util.*; public class Main{ static final int max=100005; static int a[]=new int[max]; static int b[]=new int[max]; public static void main(String[] args){ Scanner scan=new Scanner(System.in); int n=scan.nextInt(); int m=scan.nextInt(); long x=scan.nextLong(); for(int i=0;i<n;i++) a[i]=scan.nextInt(); for(int i=0;i<m;i++) b[i]=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); break; } } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/106063.html
標籤：其他
上一篇：一文解讀多執行緒 (轉)