800. 배열 요소 의 목표 와 (더 블 포인터 알고리즘)

3103 단어
두 개의 오름차 순 정렬 을 위 한 질서 있 는 배열 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;iscan.nextInt();
        for(int i=0;iscan.nextInt();
        for(int i=0,j=m-1;i){
              while(j>=0 && a[i]+b[j]>x) j--;
              if(a[i]+b[j]==x){
                    System.out.println(i+" "+j);
                    break;
              }
        }
    }
}
데이터 구조의 순환 대기 열
leetcode 알고리즘 문제 8: 문자열 변환 정수 (atoi)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage